Constraint satisfaction problem: Difference between revisions

Revision as of 06:35, 19 July 2024

Latest revision as of 22:02, 19 June 2025

(16 intermediate revisions by 8 users not shown)

Line 6:

Examples of problems that can be modeled as a constraint satisfaction problem include:

* [[Type inference]]<ref>Chandra, Satish,{{cite etbook al. "[|chapter-url=https://cs.drexel.edu/~csgordon/papers/oopsla16.pdf |doi=10.1145/2983990.2984017 |chapter=Type inference for static compilation of JavaScript]." |title=Proceedings of the 2016 ACM SIGPLAN NoticesInternational 51.10Conference (2016):on 410Object-429Oriented Programming, Systems, Languages, and Applications |date=2016 |last1=Chandra |first1=Satish |last2=Gordon |first2=Colin S. |last3=Jeannin |first3=Jean-Baptiste |last4=Schlesinger |first4=Cole |last5=Sridharan |first5=Manu |last6=Tip |first6=Frank |last7=Choi |first7=Youngil |pages=410–429 |isbn=978-1-4503-4444-9 }}</ref><ref>Jim, Trevor, and Jens Palsberg. "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.886&rep=rep1&type=pdf Type inference in systems of recursive types with subtyping]." Available on authors' web page (1999).</ref>

* [[Eight queens puzzle]]

* [[Graph coloring|Map coloring problem]]

* [[Maximum cut|Maximum cut problem]]<ref>{{Cite arXiv |eprint=1602.07674 |last1=Farhi |first1=Edward |author2=Aram W Harrow |title=Quantum Supremacy through the Quantum Approximate Optimization Algorithm |date=2016 |class=quant-ph }}</ref>

* [[Sudoku]], [[crossword]]s, [[futoshiki]], [[Kakuro]] (Cross Sums), [[Numbrix]]/[[Hidato]], [[Zebra Puzzle]], and many other [[logic puzzle]]s

These are often provided with tutorials of [[Constraint programming|CP]], ASP, Boolean SAT and SMT solvers. In the general case, constraint problems can be much harder, and may not be expressible in some of these simpler systems. "Real life" examples include [[automated planning]],<ref name="GhallabNau2004">{{cite book|author1=Malik Ghallab|author2=Dana Nau|author3=Paolo Traverso|title=Automated Planning: Theory and Practice|url=https://books.google.com/books?id=uYnpze57MSgC&q=%22constraint+satisfaction%22&pg=PP1|date=21 May 2004|publisher=Elsevier|isbn=978-0-08-049051-9|pages=1–}}</ref><ref>[http://www.cs.st-andrews.ac.uk/~ianm/docs/Thesis.ppt Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning], {{webarchive|url=https://web.archive.org/web/20090206055207/http://www.cs.st-andrews.ac.uk/~ianm/docs/Thesis.ppt |date=2009-02-06 }} Ian Miguel – slides.</ref> [[lexical disambiguation]],<ref>Demetriou, George C. "[http://www.aclweb.org/anthology/E93-1051 Lexical disambiguation using constraint handling in Prolog (CHIP)]." Proceedings of the sixth conference on European chapter of the Association for Computational Linguistics. Association for Computational Linguistics, 1993.</ref><ref>MacDonald, Maryellen C., and Mark S. Seidenberg. "[https://web.archive.org/web/20180325105726/https://pdfs.semanticscholar.org/a73e/53c44f1e998c5a03b9cbac9e0e16d5b09e77.pdf Constraint satisfaction accounts of lexical and sentence comprehension]." Handbook of Psycholinguistics (Second Edition). 2006. 581–611.</ref> [[musicology]],<ref>Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. "[http://www.jatit.org/volumes/Vol86No2/17Vol86No2.pdf GELISP: A FRAMEWORK TO REPRESENT MUSICAL CONSTRAINT SATISFACTION PROBLEMS AND SEARCH STRATEGIES]." Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327–331.</ref> [[Configure, price and quote|product configuration]]<ref>''Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules'', Dong Yang & Ming Dong, [[Journal of Intelligent Manufacturing]] volume 24, pages99–111 (2013)</ref> and [[resource allocation]].<ref>Modi, Pragnesh Jay, et al. "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.8697&rep=rep1&type=pdf A dynamic distributed constraint satisfaction approach to resource allocation]." International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2001.</ref>

Line 22:

* <math>C = \{C_1, \ldots, C_m\}</math> is a set of constraints.

Each variable <math>X_i</math> can take on the values in the nonempty ___domain <math>D_i</math>.

Every constraint <math>C_j \in C</math> is in turn a pair <math>\langle t_j,R_j \rangle</math>, where <math>t_j \subseteq X\{1, 2, \ldots, n\}</math> is a subsetset of <math>k</math> variablesindices and <math>R_j</math> is a <math>k</math>-ary [[relation (mathematics)|relation]] on the corresponding subsetproduct of domains <math>D_j\times_{i \in t_j} D_i</math> where the product is taken with indices in ascending order. An ''evaluation'' of the variables is a function from a subset of variables to a particular set of values in the corresponding subset of domains. An evaluation <math>v</math> satisfies a constraint <math>\langle t_j, R_j \rangle</math> if the values assigned to the variables <math>t_j</math> satisfy the relation <math>R_j</math>.

An evaluation is ''consistent'' if it does not violate any of the constraints. An evaluation is ''complete'' if it includes all variables. An evaluation is a ''solution'' if it is consistent and complete; such an evaluation is said to ''solve'' the constraint satisfaction problem.

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

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

* all first-order reducts of the universal homogenous [[Partially ordered set|poset]],<ref>{{Cite journalbook |last1=Kompatscher |first1=Michael |last2=Pham |first2=Trung Van |date=2017 |titlechapter= A Complexity Dichotomy for Poset Constraint Satisfaction |urltitle=https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.34th Symposium on Theoretical Aspects of Computer Science (STACS. 2017.47) |journalseries=Leibniz International Proceedings in Informatics |volume=66 |pages=DROPS-IDN/V2/Document/10.4230/LIPIcs.STACS.2017.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>

Line 56:

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]