The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
Article No.: 5, Pages 1 - 26
Abstract
Let 𝔸 be an idempotent algebra on a finite domain. By mediating between results of Chen [1] and Zhuk [2], we argue that if 𝔸 satisfies the polynomially generated powers property (PGP) and ℬ is a constraint language invariant under 𝔸 (i.e., in Inv(𝔸)), then QCSP ℬ is in NP. In doing this, we study the special forms of PGP, switchability, and collapsibility, in detail, both algebraically and logically, addressing various questions such as decidability on the way.
We then prove a complexity-theoretic converse in the case of infinite constraint languages encoded in propositional logic, that if Inv}(𝔸) satisfies the exponentially generated powers property (EGP), then QCSP (Inv(𝔸)) is co-NP-hard. Since Zhuk proved that only PGP and EGP are possible, we derive a full dichotomy for the QCSP, justifying what we term the Revised Chen Conjecture. This result becomes more significant now that the original Chen Conjecture (see [3]) is known to be false [4].
Switchability was introduced by Chen [1] as a generalization of the already-known collapsibility [5]. There, an algebra 𝔸 :=({ 0,1,2};r) was given that is switchable and not collapsible. We prove that, for all finite subsets Δ of Inv (𝔸 A), Pol (Δ) is collapsible. The significance of this is that, for QCSP on finite structures, it is still possible all QCSP tractability (in NP) explained by switchability is already explained by collapsibility. At least, no counterexample is known to this.
References
[1]
Hubie Chen. 2011. Quantified constraint satisfaction and the polynomially generated powers property. Algebra Universalis 65, 3 (2011), 213–241. DOI:
[2]
Dmitriy Zhuk. 2019. The size of generating sets of powers. Journal of Combinatorial Theory, Series A 167 (2019), 91–103.
[3]
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. Lecture Notes in Computer Science, Vol. 7230. Springer, 35–49.
[4]
Dmitriy Zhuk and Barnaby Martin. 2020. QCSP monsters and the demise of the Chen Conjecture. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy (Eds.). ACM, New York, NY, 91–104. DOI:
[5]
Hubie Chen. 2008. The complexity of quantified constraint satisfaction: Collapsibility, sink algebras, and the three-element case. SIAM Journal on Computing 37, 5 (2008), 1674–1701. DOI:
[6]
A. Bulatov, P. Jeavons, and A. Krokhin. 2005. The complexity of constraint satisfaction: An algebraic approach. In Structural Theory of Automata, Semigroups, and Universal Algebra. NATO Science Series II: Mathematics, Physics and Chemistry, Vol. 207. Springer, 181–213.
[7]
Libor Barto, Andrei A. Krokhin, and Ross Willard. 2017. Polymorphisms, and how to use them. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei A. Krokhin and Stanislav Zivný (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 1–44. DOI:
[8]
Libor Barto and Marcin Kozik. 2017. Absorption in universal algebra and CSP. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei A. Krokhin and Stanislav Zivný (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 45–77. DOI:
[9]
Florent R. Madelaine and Barnaby Martin. 2012. On the complexity of the model checking problem. CoRR abs/1210.6893 (2012). http://arxiv.org/abs/1210.6893
[10]
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).
[11]
D. Zhuk. 2017. A proof of CSP Dichotomy Conjecture. In Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS’17). 331–342. DOI:
[12]
Dmitriy Zhuk. 2020. A proof of the CSP Dichotomy Conjecture. Journal of the ACM 67, 5 (2020), Article 30, 78 pages. DOI:
[13]
Uwe Egly, Thomas Eiter, Hans Tompits, and Stefan Woltran. 2000. Solving advanced reasoning tasks using quantified Boolean formulas. In Proceedings of the 17th National Conference on Artificial Intelligence and the 12th Conference on Innovative Applications of Artificial Intelligence. 417–422.
[14]
James Wiegold. 1987. Growth sequences of finite semigroups. Journal of the Australian Mathematical Society, Series A 43, 1 (Aug. 1987), 16–20. DOI:
[15]
Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolinek. 2015. The complexity of general-valued CSPs. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS’15). 1246–1258. DOI:
[16]
Catarina Carvalho, Barnaby Martin, and Dmitriy Zhuk. 2017. The complexity of quantified constraints using the algebraic formulation. In Proceedings of the 2017 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS’17). Article 27, 14 pages. DOI:
[17]
Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. 2001. Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications 7. SIAM.
[18]
Manuel Bodirsky and Jan Kára. 2008. The complexity of equality constraint languages. Theory of Computing Systems 3, 2 (2008), 136–158.
[19]
Hubie Chen and Peter Mayr. 2016. Quantified constraint satisfaction on monoids. In Proceedings of the 25th EACSL Annual Conference on Computer Science Logic (CSL’16). Article 15, 14 pages. DOI:
[20]
Dmitriy Zhuk. 2018. A modification of the CSP algorithm for infinite languages. CoRR abs/1803.07465 (2018). arxiv:1803.07465
[21]
Catarina Carvalho, Florent R. Madelaine, and Barnaby Martin. 2015. From complexity to algebra and back: Digraph classes, collapsibility and the PGP. In Proceedings of the 2015 30th Annual IEEE Symposium on Logic in Computer Science (LICS’15).
[22]
Hubie Chen, Florent Madelaine, and Barnaby Martin. 2008. Quantified constraints and containment problems. In Proceedings of the 2008 23rd Annual IEEE Symposium on Logic in Computer Science(LICS’08). 317–328.
[23]
Florent R. Madelaine and Barnaby Martin. 2012. Containment, equivalence and coreness from CSP to QCSP and beyond. In Principles and Practice of Constraint Programming. Lecture Notes in Computer Science, Vol. 7514. Springer, 480–495. DOI:
[24]
Barnaby Martin. 2011. QCSP on partially reflexive forests. In Proceedings of the 2011 17th International Conference on Principles and Practice of Constraint Programming (CP’11).
[25]
Barnaby Martin and Florent Madelaine. 2006. Towards a trichotomy for quantified H-coloring. In Logical Approaches to Computational Barriers. Lecture Notes in Computer Science, Vol. 3988. Springer, 342–352.
[26]
Florent R. Madelaine and Barnaby Martin. 2011. A tetrachotomy for positive first-order logic without equality. In Proceedings of the 2011 26th Annual IEEE Symposium on Logic in Computer Science (LICS’11). 311–320.
[27]
Florent R. Madelaine and Barnaby Martin. 2009. The complexity of positive first-order logic without equality. In Proceedings of the 2009 24th Annual IEEE Symposium on Logic in Computer Science (LICS’09). IEEE, Los Alamitos, CA, 429–438.
[28]
Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley.
[29]
Manuel Bodirsky and Hubie Chen. 2010. Quantified equality constraints. SIAM Journal on Computing 39, 8 (2010), 3682–3699.
[30]
Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, and Andrei A. Krokhin. 2009. The complexity of constraint satisfaction games and QCSP. Information and Computation 207, 9 (2009), 923–944.
[31]
Catarina Carvalho, Barnaby Martin, and Dmitriy Zhuk. 2017. The complexity of quantified constraints. CoRR abs/1701.04086 (2017). arXiv:1701.04086
[32]
Dmitriy Zhuk. 2021. The complexity of the quantified CSP having the polynomially generated powers property. arXiv preprint arXiv:2110.09504 (2021).
Index Terms
- The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
Recommendations
The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
The constraint satisfaction probem (CSP) is a well-acknowledged framework in which many combinatorial search problems can be naturally formulated. The CSP may be viewed as the problem of deciding the truth of a logical sentence consisting of a ...
Hard constraint satisfaction problems have hard gaps at location 1
An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many ...
QCSP monsters and the demise of the chen conjecture
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingWe 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 3 elements which contains all constants. In particular, such ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2023
326 pages
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 ACM 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: 18 January 2023
Online AM: 17 October 2022
Accepted: 24 June 2022
Revised: 14 June 2022
Received: 14 July 2021
Published in TOCL Volume 24, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 105Total Downloads
- Downloads (Last 12 months)44
- Downloads (Last 6 weeks)4
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format