research-article

A Proof of the CSP Dichotomy Conjecture

Author:

Dmitriy ZhukAuthors Info & Claims

Journal of the ACM (JACM), Volume 67, Issue 5

Article No.: 30, Pages 1 - 78

https://doi.org/10.1145/3402029

Published: 26 August 2020 Publication History

Abstract

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. The standard way to parameterize interesting subclasses of the constraint satisfaction problem is via finite constraint languages. The main problem is to classify those subclasses that are solvable in polynomial time and those that are NP-complete. It was conjectured that if a constraint language has a weak near-unanimity polymorphism then the corresponding constraint satisfaction problem is tractable; otherwise, it is NP-complete.

In the article, we present an algorithm that solves Constraint Satisfaction Problem in polynomial time for constraint languages having a weak near unanimity polymorphism, which proves the remaining part of the conjecture.¹

References

[1]

Libor Barto and Alexandr Kazda. 2016. Deciding absorption. Int. J. Algebr. Comput. 26, 5 (2016), 1033--1060.

[2]

Libor Barto and Marcin Kozik. 2012. Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Logic. Methods Comput. Sci. 8, 1 (February 2012).

[3]

Libor Barto and Marcin Kozik. 2017. Absorption in universal algebra and CSP. The Constraint Satisfaction Problem: Complexity and Approximability (2017), 45 pages.

[4]

Libor Barto, Marcin Kozik, and Todd Niven. 2009. The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM J. Comput. 38, 5 (2009), 1782--1802.

Digital Library

[5]

Libor Barto, Marcin Kozik, and Ross Willard. 2012. Near unanimity constraints have bounded pathwidth duality. In Proceedings of the 2012 27th Annual IEEE Symposium on Logic in Computer Science. IEEE, 125--134.

Digital Library

[6]

Libor Barto, Andrei Krokhin, and Ross Willard. 2017. Polymorphisms, and how to use them. In Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[7]

Libor Barto and Michael Pinsker. 2016. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In Proceedings of the 2016 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 1--8.

Digital Library

[8]

Clifford Bergman. 2011. Universal Algebra: Fundamentals and Selected Topics. CRC Press.

[9]

Manuel Bodirsky. 2012. Complexity classification in infinite-domain constraint satisfaction. arXiv preprint arXiv:1201.0856 (2012).

[10]

Manuel Bodirsky and Martin Grohe. 2008. Non-dichotomies in constraint satisfaction complexity. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 184--196.

Digital Library

[11]

Manuel Bodirsky and Jan Kára. 2010. The complexity of temporal constraint satisfaction problems. J. ACM 57, 2 (2010), 9.

Digital Library

[12]

Manuel Bodirsky and Marcello Mamino. 2017. Constraint satisfaction problems over numeric domains. In Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[13]

V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov. 1969. Galois theory for Post algebras. I. Kibernetika3 (1969), 1--10. [in Russian]

[14]

V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov. 1969. Galois theory for Post algebras. II. Kibernetika5 (1969), 1--9. [in Russian]

[15]

Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, and Andrei A. Krokhin. 2009. The complexity of constraint satisfaction games and QCSP. Inf. Comput. 207, 9 (2009), 923--944.

Digital Library

[16]

Joshua Brakensiek and Venkatesan Guruswami. 2018. Promise constraint satisfaction: Structure theory and a symmetric boolean dichotomy. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1782--1801.

[17]

Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. 2005. Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34, 3 (March 2005), 720--742.

Digital Library

[18]

Andrei A. Bulatov. 2003. Tractable conservative constraint satisfaction problems. In Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, 2003. IEEE, 321--330.

Digital Library

[19]

Andrei A. Bulatov. 2006. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53, 1 (January 2006), 66--120.

Digital Library

[20]

Andrei A. Bulatov. 2017. A dichotomy theorem for nonuniform CSPs. CoRR abs/1703.03021 (2017), https://arxiv.org/abs/1703.03021v1,.

[21]

Andrei A. Bulatov. 2017. A dichotomy theorem for nonuniform CSPs. In Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS’17). IEEE, 319--330.

[22]

Andrei A. Bulatov and Matthew A. Valeriote. 2008. Recent results on the algebraic approach to the CSP. In Complexity of Constraints, Nadia Creignou, Phokion G. Kolaitis, and Heribert Vollmer (Eds.). Lecture Notes in Computer Science, Vol. 5250. Springer, Berlin, 68--92.

[23]

Jakub Bulín, Andrei Krokhin, and Jakub Opršal. 2019. Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ACM, 602--613.

Digital Library

[24]

Catarina Carvalho, Barnaby Martin, and Dmitriy Zhuk. 2017. The complexity of quantified constraints using the algebraic formulation. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, (MFCS’17). 27:1–27:14.

[25]

Hubie Chen. 2008. The complexity of quantified constraint satisfaction: Collapsibility, sink algebras, and the three-element case. SIAM J. Comput. 37, 5 (2008), 1674--1701.

Digital Library

[26]

Hubie Chen. 2012. Meditations on quantified constraint satisfaction. In Logic and Program Semantics—Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday. 35--49.

[27]

Hubie Chen. 2014. An algebraic hardness criterion for surjective constraint satisfaction. Algebr. Univers. 72, 4 (2014), 393--401.

[28]

Martin C. Cooper. 1994. Characterising tractable constraints. Artif. Intell. 65, 2 (1994), 347--361.

Digital Library

[29]

Tomás Feder and Moshe Y. Vardi. 1999. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput. 28, 1 (February 1999), 57--104.

[30]

Miron Ficak, Marcin Kozik, Miroslav Olsák, and Szymon Stankiewicz. 2019. Dichotomy for symmetric Boolean PCSPs. In 46th International Colloquium on Automata, Languages, and Programming (ICALP'19). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[31]

Ralph Freese and Ralph McKenzie. 1987. Commutator Theory for Congruence Modular Varieties. Vol. 125. Cambridge University Press Archive.

[32]

David Geiger. 1968. Closed systems of functions and predicates. Pac. J. Math. 27, 1 (1968), 95--100.

[33]

Werner H. Greub. 2012. Linear Algebra. Vol. 23. Springer Science 8 Business Media.

[34]

Pavol Hell and Jaroslav Nešetřil. 1990. On the complexity of H-coloring. J. Combin. Theory Ser. B 48, 1 (1990), 92--110.

Digital Library

[35]

PaweŁ Idziak, Petar Marković, Ralph McKenzie, Matthew Valeriote, and Ross Willard. 2010. Tractability and learnability arising from algebras with few subpowers. SIAM J. Comput. 39, 7 (2010), 3023--3037.

Digital Library

[36]

M. Istinger and H. K. Kaiser. 1979. A characterization of polynomially complete algebras. J. Algebr. 56, 1 (1979), 103--110.

[37]

Peter Jeavons. 1998. On the algebraic structure of combinatorial problems. Theor. Comput. Sci. 200, 1--2 (1998), 185--204.

Digital Library

[38]

Peter Jeavons, David Cohen, and Marc Gyssens. 1997. Closure properties of constraints. J. ACM 44, 4 (July 1997), 527--548.

Digital Library

[39]

Peter G. Jeavons and Martin C. Cooper. 1995. Tractable constraints on ordered domains. Artif. Intell. 79, 2 (1995), 327--339.

Digital Library

[40]

K. A. Kearnes and Á. Szendrei. 2012. Clones of algebras with parallelogram terms. Int. J. Algebr. Comput. 22, 1 (2012).

[41]

Lefteris M. Kirousis. 1993. Fast parallel constraint satisfaction. Artif. Intell. 64, 1 (1993), 147--160.

Digital Library

[42]

Vladimir Kolmogorov, Andrei Krokhin, and Michal Rolinek. 2017. The complexity of general-valued CSPs. SIAM J. Comput. 46, 3 (2017), 1087--1110.

Digital Library

[43]

Marcin Kozik. 2016. Weak consistency notions for all the CSPs of bounded width. In Proceedings of the 2016 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’16). IEEE, 1--9.

Digital Library

[44]

D. Lau. 2006. Function Algebras on Finite Sets. Springer.

[45]

Hans Lausch and Wilfred Nobauer. 2000. Algebra of Polynomials. Vol. 5. Elsevier.

[46]

A. K. Mackworth. 1977. Consistency in networks of relations. Artif. Intell. 8, 1 (1977), 99--118.

Digital Library

[47]

Miklós Maróti. 2011. Tree on top of Malcev. Retrieved from http://www.math.u-szeged.hu/~mmaroti/pdf/200x%20Tree%20on%20top%20of%20Maltsev.pdf (2011).

[48]

M. Maróti and R. Mckenzie. 2008. Existence theorems for weakly symmetric operations. Algebr. Univers. 59, 3–4 (2008), 463--489.

[49]

Barnaby Martin. 2017. Quantified constraints in twenty seventeen. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav Zivny (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 327--346.

[50]

U. Montanari. 1974. Networks of constraints: Fundamental properties and applications to picture processing. Inf. Sci. 7 (1974), 95--132.

[51]

Antoine Mottet and Manuel Bodirsky. 2018. A dichotomy for first-order reducts of unary structures. Logic. Methods Comput. Sci. 14, 2 (2018).

[52]

E. L. Post. 1941. The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press, Princeton, NJ.

[53]

I. Rosenberg. 1970. Über die funktionale Vollständigkeit in den mehrwertigen Logiken. Rozpravy Československe Akad. Věd., Ser. Math. Nat. Sci. 80 (1970), 3--93.

[54]

Thomas J. Schaefer. 1978. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC’78). ACM, New York, NY, 216--226.

Digital Library

[55]

Thomas Schiex, Helene Fargier, Gerard Verfaillie, et al. 1995. Valued constraint satisfaction problems: Hard and easy problems. Int. Joint Conf. Artif. Intell. 1, 95 (1995), 631--639.

[56]

Ross Willard. 2019. Similarity, critical relations, and Zhuk’s bridges. In Proceedings of the 98th Workshop on General Algebra: Arbeitstagung Allgemeine Algebra (AAA98).

[57]

Dmitriy Zhuk. 2011. The Lattice of Closed Classes of Self-dual Functions in Three-valued Logic. Izdatelstvo MGU. [in Russian]

[58]

Dmitriy Zhuk. 2011. The predicate method to construct the Post lattice. Discr. Math. Appl. 21, 3 (2011), 329--344.

[59]

Dmitriy Zhuk. 2012. The cardinality of the set of all clones containing a given minimal clone on three elements. Algebr. Univers. 68, 3–4 (2012), 295--320.

[60]

Dmitriy Zhuk. 2014. The existence of a near-unanimity function is decidable. Algebr. Univers. 71, 1 (2014), 31--54.

[61]

Dmitriy Zhuk. 2015. The lattice of all clones of self-dual functions in three-valued logic. J. Mult.-Valued Logic Soft Comput. 24, 1–4 (2015), 251--316.

[62]

Dmitriy Zhuk. 2017. Key (critical) relations preserved by a weak near-unanimity function. Algebr. Univers. 77, 2 (2017), 191--235.

[63]

Dmitriy Zhuk. 2018. A modification of the CSP algorithm for infinite languages. arXiv preprint arXiv:1803.07465 (2018).

[64]

Dmitriy Zhuk and Barnaby Martin. 2019. QCSP monsters and the demise of the Chen Conjecture. arXiv preprint arXiv:1907.00239 (2019).

[65]

Dmitriy Zhuk. 2017. A proof of CSP dichotomy conjecture. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS'17), Berkeley, CA, USA, October 15-17, 2017. 331--342.

Cited By

Mottet APinsker M(2024)Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structuresJournal of the ACM10.1145/368920771:5(1-47)Online publication date: 17-Aug-2024
https://dl.acm.org/doi/10.1145/3689207
Nakajima TŽivný S(2024)On the Complexity of Symmetric vs. Functional PCSPsACM Transactions on Algorithms10.1145/367365520:4(1-29)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3673655
Ciardo LSobocinski PLago UEsparza J(2024)Quantum advantage and CSP complexityProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662118(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662118
Show More Cited By

Index Terms

A Proof of the CSP Dichotomy Conjecture
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity theory and logic
  2. Logic
    1. Constraint and logic programming

Recommendations

QCSP Monsters and the Demise of the Chen Conjecture
We give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language Γ, QCSP(Γ), where Γ is a finite language over three elements that contains all constants. In particular, such ...
Complexity of approximating CSP with balance / hard constraints
ITCS '14: Proceedings of the 5th conference on Innovations in theoretical computer science

We study two natural extensions of Constraint Satisfaction Problems (CSPs). Balance-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of Hard-Max-CSP consists of soft constraints ...
A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs

We determine the computational complexity of approximately counting the total weight of variable assignments for every complex-weighted Boolean constraint satisfaction problem (or CSP) with any number of additional unary (i.e., arity 1) constraints, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 67, Issue 5

October 2020

274 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3420255

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 August 2020

Accepted: 01 May 2020

Revised: 01 May 2020

Received: 01 December 2017

Published in JACM Volume 67, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Russian Foundation for Basic Research
European Research Council (ERC)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

72
Total Citations
View Citations
632
Total Downloads

Downloads (Last 12 months)122
Downloads (Last 6 weeks)14

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mottet APinsker M(2024)Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structuresJournal of the ACM10.1145/368920771:5(1-47)Online publication date: 17-Aug-2024
https://dl.acm.org/doi/10.1145/3689207
Nakajima TŽivný S(2024)On the Complexity of Symmetric vs. Functional PCSPsACM Transactions on Algorithms10.1145/367365520:4(1-29)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3673655
Ciardo LSobocinski PLago UEsparza J(2024)Quantum advantage and CSP complexityProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662118(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662118
Barto LButti SKazda AViola CŽivný SSobocinski PLago UEsparza J(2024)Algebraic Approach to ApproximationProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662076(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662076
Banakh DKozik MSobocinski PLago UEsparza J(2024)Injective hardness condition for PCSPsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662072(1-10)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662072
Bodirsky MSemanišinová ŽLutz CSobocinski PLago UEsparza J(2024)The Complexity of Resilience Problems via Valued Constraint Satisfaction ProblemsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662071(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662071
Ciardo LKozik MKrokhin ANakajima TŽivný SSobocinski PLago UEsparza J(2024)1-in-3 vs. Not-All-Equal: Dichotomy of a broken promiseProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662069(1-12)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662069
Dalmau VOpršal JSobocinski PLago UEsparza J(2024)Local consistency as a reduction between constraint satisfaction problemsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662068(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662068
Koutris POuyang XWijsen J(2024)Consistent Query Answering for Primary Keys on Rooted Tree QueriesProceedings of the ACM on Management of Data10.1145/36511392:2(1-26)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651139
Ciardo LŽivný SMohar BShinkar IO'Donnell R(2024)Semidefinite Programming and Linear Equations vs. Homomorphism ProblemsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649635(1935-1943)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649635
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents