# constraint satisfaction

Also found in: Wikipedia.

## constraint satisfaction

(application)The process of assigning values to variables
while meeting certain requirements or "constraints". For
example, in graph colouring, a node is a variable, the
colour assigned to it is its value and a link between two
nodes represents the constraint that those two nodes must not
be assigned the same colour. In scheduling, constraints
apply to such variables as the starting and ending times for
tasks.

The Simplex method is one well known technique for solving numerical constraints.

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 instances of NP-complete problems 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.

The Simplex method is one well known technique for solving numerical constraints.

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 instances of NP-complete problems 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.

**Phase transitions in search**(Tad Hogg, XEROX PARC).Want to thank TFD for its existence? Tell a friend about us, add a link to this page, or visit the webmaster's page for free fun content.

Link to this page: