Constraint satisfaction problem: Difference between revisions

Revision as of 08:07, 20 November 2023

Revision as of 08:09, 20 November 2023

Line 39:

===Decision problems===

CSPs are also studied in [[computational complexity theory]] and [[finite model theory]]. An important [[dichotomy]] theorem states that for each set of relations, the set of all CSPs that can be represented using only relations chosen from that set is either in [[P (complexity)|P]] or [[NP-complete]]. CSPs thus provide one of the largest known subsets of [[NP (complexity)|NP]] which avoids [[NP-intermediate]] problems, whose existence was demonstrated by [[Ladner's theorem]] under the assumption that [[P versus NP problem|P ≠ NP]]. [[Schaefer's dichotomy theorem]] handles the case when all the available relations are [[Boolean operator (Boolean algebra)|Boolean operator]]s, that is, for ___domain size 2. Schaefer's dichotomy theorem was firstlater generalized to a larger class of relations,<ref>{{Cite book| last1 = Bodirsky | first1 = Manuel| last2 = Pinsker | first2 = Michael| doi = 10.1145/1993636.1993724 | contribution = Schaefer's theorem for graphs | publisher= [[Association for Computing Machinery]]| title = Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11)| pages = 655–664 | year = 2011 | isbn = 978-1-4503-0691-1| arxiv = 1011.2894| bibcode = 2010arXiv1011.2894B| title-link = Symposium on Theory of Computing| s2cid = 47097319}}</ref> and the full dichotomy theorem was finally proved independently by Andrei Bulatov<ref>{{Cite book| last1 = Bulatov | first1 = Andrei | doi = 10.1109/FOCS.2017.37 | contribution = A Dichotomy Theorem for Nonuniform CSPs | publisher = IEEE Computer Society | title = Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 | pages = 319-330 | year = 2017 | }}</ref> and Dmitriy Zhuk.<ref>{{Cite article| last1 = Zhuk | first1 = Dmitriy | doi = 10.1145/3402029 | title = A Proof of the CSP Dichotomy Conjecture | journal = Journal of the ACM | volume = 67 | number = 5 | pages = 1–78 | year = 2020}}</ref>

Most classes of CSPs that are known to be tractable are those where the [[hypergraph]] of constraints has bounded [[treewidth]] (and there are no restrictions on the set of constraint relations), or where the constraints have arbitrary form but there exist essentially non-unary polymorphisms{{Clarify|date=February 2009}} of the set of constraint relations.