Constraint satisfaction

Constraint satisfaction is the group of problems in which finding the solution involves discovering a suitable group of parameters such that the that result falls with some pre-defined boundaries. Many real-world problems can be described as constraint satisfaction problems (CSPs). Engineering is a CSP where an object must be specified with a certain cost that performs a given task. Airline routing is a CSP where cost and customer satisfaction are constraints. Coloring a map using a limited number of colors is a CSP. Designing software can even be described as a CSP where program size, memory usage, cost to produce, the average time it takes a user to complete a task etc. are constraints.

Many NP-complete problems are constraint satisfaction problems (e.g. boolean satisfiability where a set of input truth values must be found that causes a statement of propositional logic to be true). Because the consensus is that NP-complete problems are intractable (cannot be solved on a computer in time polynomial to the size of the problem), even with quantum computing, it is likely that in general constraint satisfaction problems cannot be solved perfectly. Because of the importance of CSPs in the real world, and the difficulty in solving them, developing algorithms to efficiently solve CSPs is an important field. Algorithms can be designed that attempt to find a perfect solution in the smallest amount of time, or find the best possible solution given limited time. --ChronicElement 23:30, 6 January 2007 (UTC)