Dictionary.net

The process of assigning values to variableswhile meeting certain requirements or "constraints". Forexample, in graph colouring, a node is a variable, thecolour assigned to it is its value and a link between twonodes represents the constraint that those two nodes must notbe assigned the same colour. In scheduling, constraintsapply to such variables as the starting and ending times fortasks.The Simplex method is one well known technique for solvingnumerical constraints.The search difficulty of constraint satisfaction problems canbe determined on average from knowledge of easily computedstructural properties of the problems. In fact, hardinstances of NP-complete problems are concentrated near anabrupt transition between under- and over-constrainedproblems. This transition is analogous to phase transitionsin physical systems and offers a way to estimate the likelydifficulty of a constraint problem before attempting to solveit with search.Phase transitions in search(ftp://parcftp.xerox.com/pub/dynamics/constraints.html) (TadHogg, XEROX PARC).