The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction problems on finite domains.
Solving a constraint satisfaction problem on a finite domain is an NP-complete problem in general. Research has shown a number of polynomial-time subcases, mostly obtained by restricting either the allowed domains or constraints or the way constraints can be placed over the variables. Research has also established relationship of the constraint satisfaction problem with problems in other areas such as finite model theory and databases.
Read more about Complexity Of Constraint Satisfaction: Overview, Restrictions, Equivalence Conditions, Dichotomy Theorems, Sufficient Conditions For Tractability, Necessary Condition For Tractability
Famous quotes containing the words complexity of, complexity, constraint and/or satisfaction:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)
“In America a woman loses her independence for ever in the bonds of matrimony. While there is less constraint on girls there than anywhere else, a wife submits to stricter obligations. For the former, her father’s house is a home of freedom and pleasure; for the latter, her husband’s is almost a cloister.”
—Alexis de Tocqueville (1805–1859)
“Our manners have been corrupted by communication with the saints. Our hymn-books resound with a melodious cursing of God and enduring Him forever. One would say that even the prophets and redeemers had rather consoled the fears than confirmed the hopes of man. There is nowhere recorded a simple and irrepressible satisfaction with the gift of life, any memorable praise of God.”
—Henry David Thoreau (1817–1862)