Constraint satisfaction problem: Difference between revisions

Revision as of 13:57, 29 March 2025

Revision as of 14:23, 27 April 2025

Line 38:

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

Line 49:

* 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>