Constraint satisfaction problem: Difference between revisions

Revision as of 23:11, 26 March 2024

Revision as of 13:53, 15 July 2024

Line 38:

==Theoretical aspects==

===DecisionComputational problemsComplexity===

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 |last=Barto |first=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 |url=http://arxiv.org/abs/2104.11808 |journal=TheoretiCS |volume=Volume 3 |pages=11361 |doi=10.46298/theoretics.24.14 |issn=2751-4838}}</ref>.

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 later 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 a full dichotomy theorem was first conjectured as the Feder–Vardi conjecture<ref>{{Cite journal |last=Feder |first=Tomás |last2=Vardi |first2=Moshe Y. |author-link2=Moshe Vardi|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 |date=1998}}</ref> and 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 journal| 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| arxiv = 1704.01914 }}</ref>

Since every computational decision problem is [[Polynomial-time reduction|polynomial-time equivalent]] to a CSP with an infinite template<ref>{{Cite journal |last=Bodirsky |first=Manuel |last2=Grohe |first2=Martin |date=2008 |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=Non-dichotomies in Constraint Satisfaction Complexity |url=https://link.springer.com/chapter/10.1007/978-3-540-70583-3_16 |journal=Automata, Languages and Programming |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]].

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.

CSPsHowever, area alsolarge studiedclass inof [[computationalCSPs complexityarising theory]]from andnatural [[finiteapplications modelsatisfy theory]].a Ancomplexity important [[dichotomy]] theorem states that for each set of relations, the set of all CSPsmeaning that canevery beCSP represented using only relations chosen fromwithin that setclass 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,. whoseA existencecomplexity dichotomy was demonstratedfirst proven by [[LadnerSchaefer's dichotomy theorem|Schaefer]] underfor theBoolean assumptionCSPs, that [[P versus NP problem|P ≠ NP]]i.e. [[Schaefer'sCSPs dichotomyover theorem]]a handles2-element the___domain caseand whenwhere all the available relations are [[Boolean operator (Boolean algebra)|Boolean operator]]s, that is, for ___domain size 2. Schaefer'sThis dichotomyresult theoremhas was laterbeen generalized tofor avarious larger classclasses of relationsCSPs,<ref>{{Cite book|most last1notably =for Bodirskyall |CSPs first1over =finite Manuel| last2 = Pinsker | first2 = Michael| doi = 10domains.1145/1993636.1993724 |This 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 = 978finite-1-4503-0691-1|___domain arxivdichotomy conjecture'' was first formulated by Tomás = 1011.2894| bibcode = 2010arXiv1011.2894B| title-link = Symposium on Theory of Computing| s2cid = 47097319}}</ref>Feder and aMoshe full dichotomy theorem was first conjectured as the Feder–Vardi conjectureVardi<ref>{{Cite journal |last=Feder |first=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 |date=1998}}</ref>, and finally provedproven 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 |publisher=IEEE pagesComputer Society |year=2017 |pages=319–330 |contribution=A yearDichotomy =Theorem for Nonuniform CSPs |doi=10.1109/FOCS.2017.37}}</ref> and Dmitriy Zhuk in 2017.<ref>{{Cite journal | last1 = Zhuk | first1 = Dmitriy | doi year= 10.1145/34020292020 | title = A Proof of the CSP Dichotomy Conjecture | journal = Journal of the ACM | volume = 67 | number = 5 | pages = 1–78 | year = 2020| 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>,

* 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 |bibcode=2010arXiv1011.2894B |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 |last=Bodirsky |first=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 |issn=1529-3785}}</ref>,

* all first-order reducts of the universal homogenous [[Partially ordered set|poset]]<ref>{{Cite journal |last=Kompatscher |first=Michael |last2=Pham |first2=Trung Van |date=2017 |title=A Complexity Dichotomy for Poset Constraint Satisfaction |url=https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.47 |journal=DROPS-IDN/v2/document/10.4230/LIPIcs.STACS.2017.47 |language=en |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |doi=10.4230/LIPIcs.STACS.2017.47}}</ref>,

* all first-order reducts of homogenous undirected graphs<ref>{{Cite journal |last=Bodirsky |first=Manuel |last2=Martin |first2=Barnaby |last3=Pinsker |first3=Michael |last4=Pongrácz |first4=András |date=2019-01 |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}}</ref>,

* all first-order reducts of all unary structures<ref>{{Citation |last=Bodirsky |first=Manuel |title=A Dichotomy for First-Order Reducts of Unary Structures |date=2018-05-20 |url=http://arxiv.org/abs/1601.04520 |access-date=2024-07-15 |doi=10.23638/LMCS-14(2:13)2018 |last2=Mottet |first2=Antoine}}</ref>,

* all CSPs in the complexity class MMSNP<ref>{{Cite journal |last=Bodirsky |first=Manuel |last2=Madelaine |first2=Florent |last3=Mottet |first3=Antoine |date=2018-07-09 |title=A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP |url=https://doi.org/10.1145/3209108.3209156 |journal=Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science |series=LICS '18 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=105–114 |doi=10.1145/3209108.3209156 |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 |last=Barto |first=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 |last=Bodirsky |first=Manuel |last2=Pinsker |first2=Michael |last3=Pongrácz |first3=András |date=2021-03 |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}}</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>{{Citation |last=Pinsker |first=Michael |title=Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep |date=2022-03-31 |url=http://arxiv.org/abs/2203.17182 |access-date=2024-07-15 |doi=10.48550/arXiv.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>

Line 102 ⟶ 120:

==Further reading==

*[https://www.youtube.com/watch?v=wrs6Lvo5LZM A quick introduction to constraint satisfaction on YouTube]

*Manuel Bodirsky (2021). ''Complexity of Infinite-Domain Constraint Satisfaction''. Cambridge University Press. https://doi.org/10.1017/9781107337534

*{{cite journal|author1=Steven Minton|author2=Andy Philips|author3=Mark D. Johnston|author4=Philip Laird|title=Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems|journal=Journal of Artificial Intelligence Research|year=1993|volume=58|issue=1–3|pages=161&ndash;205|doi=10.1016/0004-3702(92)90007-k|citeseerx=10.1.1.308.6637|s2cid=14830518 }}

*{{cite book