Humble Ants solve hard problems

Quite interesting recent work show that ants can solve NP-hard problems with changing configuration in an adaptive fashion. Australian & Swedish researchers were able to demostrate it experimentally; Optimisation in a natural system: Argentine ants solve the Towers of Hanoi [doi].

Constraint Satisfaction: A glimpse of computational complexity

A generic problem appear in many different fields from computer science applications to operations research is constraint satisfaction problem (CSP). M. Jerrum gives a generic outline on the field [doi]. An article by Bulatov-Marx on global cardinality constraint has recently appeared [doi].