Constraint satisfaction problem: Difference between revisions

Revision as of 19:04, 23 May 2025

Revision as of 17:29, 24 May 2025

Line 42:

Since every computational decision problem is [[Polynomial-time reduction|polynomial-time equivalent]] to a CSP with an infinite template,<ref>{{Cite book |last1=Bodirsky |first1=Manuel |last2=Grohe |first2=Martin |chapter=Non-dichotomies in Constraint Satisfaction Complexity |series=Lecture Notes in Computer Science |date=2008 |volume=5126 |editor-last=Aceto |editor-first=Luca |editor2-last=Damgård |editor2-first=Ivan |editor3-last=Goldberg |editor3-first=Leslie Ann |editor4-last=Halldórsson |editor4-first=Magnús M. |editor5-last=Ingólfsdóttir |editor5-first=Anna |editor6-last=Walukiewicz |editor6-first=Igor |title=Automata, Languages and Programming |chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-70583-3_16 |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=184–196 |doi=10.1007/978-3-540-70583-3_16 |isbn=978-3-540-70583-3}}</ref> general CSPs can have arbitrary complexity. In particular, there are also CSPs within the class of [[NP-intermediate]] problems, whose existence was demonstrated by [[NP-intermediate|Ladner]], under the assumption that [[P versus NP problem|P ≠ NP]].

However, a large class of CSPs arising from natural applications satisfy a complexity dichotomy, meaning that every CSP within that class is either in [[P (complexity)|P]] or [[NP-complete|NP-triology math complete]]. These CSPs thus provide one of the largest known subsets of [[NP (complexity)|NP]] which avoids [[NP-intermediate]] problems. A complexity dichotomy was first proven by [[Schaefer's dichotomy theorem|Schaefer]] for Boolean CSPs, i.e. CSPs over a 2-element ___domain and where all the available relations are [[Boolean operator (Boolean algebra)|Boolean operator]]s. This result has been generalized for various classes of CSPs, most notably for all CSPs over finite domains. This ''finite-___domain dichotomy conjecture'' was first formulated by Tomás Feder and Moshe Vardi,<ref>{{Cite journal |last1=Feder |first1=Tomás |last2=Vardi |first2=Moshe Y. |author-link2=Moshe Vardi |date=1998 |title=The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory |url=http://epubs.siam.org/doi/10.1137/S0097539794266766 |journal=SIAM Journal on Computing |language=en |volume=28 |issue=1 |pages=57–104 |doi=10.1137/S0097539794266766 |issn=0097-5397}}</ref> and finally proven independently by Andrei Bulatov<ref>{{Cite book |last1=Bulatov |first1=Andrei |title=Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 |publisher=IEEE Computer Society |year=2017 |pages=319–330 |contribution=A Dichotomy Theorem for Nonuniform CSPs |doi=10.1109/FOCS.2017.37|arxiv=1703.03021 |isbn=978-1-5386-3464-6 }}</ref> and Dmitriy Zhuk in 2017.<ref>{{Cite journal |last1=Zhuk |first1=Dmitriy |year=2020 |title=A Proof of the CSP Dichotomy Conjecture |journal=Journal of the ACM |volume=67 |pages=1–78 |arxiv=1704.01914 |doi=10.1145/3402029 |number=5}}</ref>

Other classes for which a complexity dichotomy has been confirmed are