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)
“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)
“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)
“Through Plato Aristotle came to believe in God, but Plato never attempted to prove His reality. Aristotle had to do so. Plato contemplated Him; Aristotle produced arguments to demonstrate Him. Plato never defined Him, but Aristotle thought God through logically and concluded with entire satisfaction to himself that He was the Unmoved Mover.”
—Edith Hamilton (1867–1963)