[1-8] Complexity of Constraint Satisfaction (including Phase Transition)

Standard papers on this area include:

Alan Mackworth and Eugene Freuder, "The Complexity of Some
Polynomial Network Consistency Algorithms for Constraint Satisfaction
Problems", in Artificial Intelligence, 1985, 25:65-73

Alan Mackworth and Eugene Freuder, "The Complexity of Constraint
Satisfaction Revisited", in Artificial Intelligence, February 1993, 59
(1-2): 57-62,

Also Tsang's book as mentioned previously.


Phase Transitions in Constraint Satisfaction Problems
-----------------------------------------------------

The search difficulty of constraint satisfaction problems can be
determined, on average, from knowledge of easily computed structural
properties of the problems. In fact, hard problem instances are
concentrated near an abrupt transition between under- and over-
constrained problems. This transition is analogous to phase transitions
in physical systems and offers a way to estimate the likely difficulty
of a constraint problem before attempting to solve it with search.

For more information and pointers to related work, see the web page:
ftp://parcftp.xerox.com/pub/dynamics/constraints.html

Information kindly supplied by Tad Hogg <hogg@parc.xerox.com>.