Constraint satisfaction problem: Difference between revisions

Revision as of 19:04, 23 May 2025

Latest revision as of 22:02, 19 June 2025

(One intermediate revision by one other user not shown)

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|url-access=subscription }}</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

* all [[First-order logic|first-order]] [[Reduct|reducts]] of <math>(\mathbb{Q},<)</math>,<ref>{{Cite journal |last1=Bodirsky |first1=Manuel |last2=Kára |first2=Jan |date=2010-02-08 |title=The complexity of temporal constraint satisfaction problems |url=https://doi.org/10.1145/1667053.1667058 |journal=J. ACM |volume=57 |issue=2 |pages=9:1–9:41 |doi=10.1145/1667053.1667058 |issn=0004-5411|url-access=subscription }}</ref>

* all first-order reducts of the [[Rado graph|countable random graph]],<ref>{{Cite book |last1=Bodirsky |first1=Manuel |title=Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11) |title-link=Symposium on Theory of Computing |last2=Pinsker |first2=Michael |publisher=[[Association for Computing Machinery]] |year=2011 |isbn=978-1-4503-0691-1 |pages=655–664 |contribution=Schaefer's theorem for graphs |doi=10.1145/1993636.1993724 |arxiv=1011.2894 |s2cid=47097319}}</ref>

* all first-order reducts of the [[model companion]] of the class of all C-relations,<ref>{{Cite journal |last1=Bodirsky |first1=Manuel |last2=Jonsson |first2=Peter |last3=Pham |first3=Trung Van |date=2017-08-02 |title=The Complexity of Phylogeny Constraint Satisfaction Problems |url=https://doi.org/10.1145/3105907 |journal=ACM Trans. Comput. Logic |volume=18 |issue=3 |pages=23:1–23:42 |doi=10.1145/3105907 |arxiv=1503.07310 |issn=1529-3785}}</ref>