Editing Constraint satisfaction problem (section)

===Computational Complexity===
CSPs are also studied in [[computational complexity theory]], [[finite model theory]] and [[universal algebra]]. It turned out that questions about the complexity of CSPs translate into important universal-algebraic questions about underlying algebras. This approach is known as the ''algebraic approach'' to CSPs.<ref>{{Cite journal |last1=Barto |first1=Libor |last2=Brady |first2=Zarathustra |last3=Bulatov |first3=Andrei |last4=Kozik |first4=Marcin |last5=Zhuk |first5=Dmitriy |date=2024-05-15 |title=Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras |journal=Theoretics |volume=3 |pages=11361 |doi=10.46298/theoretics.24.14 |arxiv=2104.11808 |issn=2751-4838}}</ref> 

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]]. 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

* 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}}</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>
* all first-order reducts of the universal homogenous [[Partially ordered set|poset]],<ref>{{Cite book |last1=Kompatscher |first1=Michael |last2=Pham |first2=Trung Van |date=2017 |chapter= A Complexity Dichotomy for Poset Constraint Satisfaction|title=34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) |series=Leibniz International Proceedings in Informatics |volume=66 |pages=47:1–47:12 |language=en |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |doi=10.4230/LIPIcs.STACS.2017.47|doi-access=free |isbn=978-3-95977-028-6 }}</ref>
* all first-order reducts of homogenous undirected graphs,<ref>{{Cite journal |last1=Bodirsky |first1=Manuel |last2=Martin |first2=Barnaby |last3=Pinsker |first3=Michael |last4=Pongrácz |first4=András |date=January 2019 |title=Constraint Satisfaction Problems for Reducts of Homogeneous Graphs |url=https://epubs.siam.org/doi/10.1137/16M1082974 |journal=SIAM Journal on Computing |language=en |volume=48 |issue=4 |pages=1224–1264 |doi=10.1137/16M1082974 |issn=0097-5397|arxiv=1602.05819 }}</ref>
* all first-order reducts of all unary structures,<ref>{{Citation |last1=Bodirsky |first1=Manuel |title=A Dichotomy for First-Order Reducts of Unary Structures |date=2018-05-20 |doi=10.23638/LMCS-14(2:13)2018 |last2=Mottet |first2=Antoine|journal=Logical Methods in Computer Science |volume=14 |issue=2 |arxiv=1601.04520 }}</ref>
* all CSPs in the complexity class MMSNP.<ref>{{Cite book |last1=Bodirsky |first1=Manuel |last2=Madelaine |first2=Florent |last3=Mottet |first3=Antoine |chapter=A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP |date=2018-07-09 |title=Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science |chapter-url=https://doi.org/10.1145/3209108.3209156 |series=LICS '18 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=105–114 |doi=10.1145/3209108.3209156 |arxiv=1802.03255 |isbn=978-1-4503-5583-4}}</ref>

Most classes of CSPs that are known to be tractable are those where the [[hypergraph]] of constraints has bounded [[treewidth]],<ref>{{Cite journal |last1=Barto |first1=Libor |last2=Kozik |first2=Marcin |date=2014-01-01 |title=Constraint Satisfaction Problems Solvable by Local Consistency Methods |url=https://doi.org/10.1145/2556646 |journal=J. ACM |volume=61 |issue=1 |pages=3:1–3:19 |doi=10.1145/2556646 |issn=0004-5411}}</ref> or where the constraints have arbitrary form but there exist equationally non-trivial polymorphisms of the set of constraint relations.<ref>{{Cite book |last=Bodirsky |first=Manuel |url=https://www.cambridge.org/core/books/complexity-of-infinitedomain-constraint-satisfaction/8E6E86C8F8C5C534440266EFB9E584D3 |title=Complexity of Infinite-Domain Constraint Satisfaction |date=2021 |publisher=Cambridge University Press |isbn=978-1-107-04284-1 |series=Lecture Notes in Logic |location=Cambridge}}</ref>

An ''infinite-domain dichotomy conjecture''<ref>{{Cite journal |last1=Bodirsky |first1=Manuel |last2=Pinsker |first2=Michael |last3=Pongrácz |first3=András |date=March 2021 |title=Projective Clone Homomorphisms |url=https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/projective-clone-homomorphisms/3654D0B62D3C45DF6DBD93DDC57B8B02 |journal=The Journal of Symbolic Logic |language=en |volume=86 |issue=1 |pages=148–161 |doi=10.1017/jsl.2019.23 |issn=0022-4812|arxiv=1409.4601 |hdl=2437/268560 }}</ref> has been formulated for all CSPs of reducts of finitely bounded homogenous structures, stating that the CSP of such a structure is in P if and only if its [[Clone (algebra)|polymorphism clone]] is equationally non-trivial, and NP-hard otherwise. 

The complexity of such infinite-domain CSPs as well as of other generalisations (Valued CSPs, Quantified CSPs, Promise CSPs) is still an area of active research.<ref>{{cite arXiv |last=Pinsker |first=Michael |title=Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep |date=2022-03-31 |class=cs.LO |eprint=2203.17182}}</ref>[https://tu-dresden.de/tu-dresden/newsportal/news/erc-synergy-grant-fuer-pococop-komplexitaet-von-berechnungen?set_language=en][https://www.tuwien.at/tu-wien/aktuelles/news/erc-synergy-grant-die-komplexitaet-von-berechnungen]

Every CSP can also be considered as a [[conjunctive query]] containment problem.<ref>{{Cite journal| last1 = Kolaitis| first1 = Phokion G.| last2 = Vardi| first2 = Moshe Y.| author-link2 = Moshe Y. Vardi| title = Conjunctive-Query Containment and Constraint Satisfaction| journal = [[Journal of Computer and System Sciences]]| volume = 61| issue = 2| pages = 302–332| year = 2000| doi = 10.1006/jcss.2000.1713 | doi-access = free}}</ref>