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)
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)
“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)
“Besides, our action on each other, good as well as evil, is so incidental and at random, that we can seldom hear the acknowledgments of any person who would thank us for a benefit, without some shame and humiliation. We can rarely strike a direct stroke, but must be content with an oblique one; we seldom have the satisfaction of yielding a direct benefit, which is directly received.”
—Ralph Waldo Emerson (1803–1882)