The Complexity of Quantified Constraints Using the Algebraic Formulation

Carvalho, Catarina; Martin, Barnaby; Zhuk, Dmitriy

doi:10.4230/LIPIcs.MFCS.2017.27

File

LIPIcs.MFCS.2017.27.pdf

Filesize: 478 kB
14 pages

Document Identifiers

DOI: 10.4230/LIPIcs.MFCS.2017.27
URN: urn:nbn:de:0030-drops-80793

Author Details

Catarina Carvalho

Barnaby Martin

Dmitriy Zhuk

Cite AsGet BibTex

Catarina Carvalho, Barnaby Martin, and Dmitriy Zhuk. The Complexity of Quantified Constraints Using the Algebraic Formulation. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.27

Abstract

Let A be an idempotent algebra on a finite domain. We combine results of Chen, Zhuk and Carvalho et al. to argue that if A satisfies the polynomially generated powers property (PGP), then QCSP(Inv(A)) is in NP. We then use the result of Zhuk to prove a converse, that if Inv(A) satisfies the exponentially generated powers property (EGP), then QCSP(Inv(A)) is co-NP-hard. Since Zhuk proved that only PGP and EGP are possible, we derive a full dichotomy for the QCSP, justifying the moral correctness of what we term the Chen Conjecture. We examine in closer detail the situation for domains of size three. Over any finite domain, the only type of PGP that can occur is switchability. Switchability was introduced by Chen as a generalisation of the already-known Collapsibility. For three-element domain algebras A that are Switchable, we prove that for every finite subset Delta of Inv(A), Pol(Delta) is Collapsible. The significance of this is that, for QCSP on finite structures (over three-element domain), all QCSP tractability explained by Switchability is already explained by Collapsibility. Finally, we present a three-element domain complexity classification vignette, using known as well as derived results.

Keywords

Quantified Constraints
Computational Complexity
Universal Algebra
Constraint Satisfaction

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Manuel Bodirsky and Hubie Chen. Quantified equality constraints. SIAM J. Comput., 39(8):3682-3699, 2010. URL: http://dx.doi.org/10.1137/080725209.
Manuel Bodirsky and Jan Kára. The complexity of equality constraint languages. Theory of Computing Systems, 3(2):136-158, 2008. A conference version appeared in the proceedings of CSR'06.
Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, and Andrei A. Krokhin. The complexity of constraint satisfaction games and qcsp. Inf. Comput., 207(9):923-944, 2009. URL: http://dx.doi.org/10.1016/j.ic.2009.05.003.
A. Bulatov, A. Krokhin, and P. G. Jeavons. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34:720-742, 2005.
Catarina Carvalho, Florent R. Madelaine, and Barnaby Martin. From complexity to algebra and back: digraph classes, collapsibility and the PGP. In 30th Annual IEEE Symposium on Logic in Computer Science (LICS), 2015.
Hubie Chen. The complexity of quantified constraint satisfaction: Collapsibility, sink algebras, and the three-element case. SIAM J. Comput., 37(5):1674-1701, 2008. URL: http://dx.doi.org/10.1137/060668572.
Hubie Chen. Quantified constraint satisfaction and the polynomially generated powers property. Algebra universalis, 65(3):213-241, 2011. An extended abstract appeared in ICALP B 2008. URL: http://dx.doi.org/10.1007/s00012-011-0125-4.
Hubie Chen. Meditations on quantified constraint satisfaction. In Logic and Program Semantics - Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday, pages 35-49, 2012. URL: http://dx.doi.org/10.1007/978-3-642-29485-3_4.
Hubie Chen and Peter Mayr. Quantified constraint satisfaction on monoids, 2016.
Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications 7, 2001.
Uwe Egly, Thomas Eiter, Hans Tompits, and Stefan Woltran. Solving advanced reasoning tasks using quantified boolean formulas. In Proc. 17th Nat. Conf. on Artificial Intelligence and 12th Conf. on Innovative Applications of Artificial Intelligence, pages 417-422. AAAI Press/ The MIT Press, 2000.
T. Feder and M. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing, 28:57-104, 1999.
Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolinek. The complexity of general-valued csps. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1246-1258, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.80.
Florent R. Madelaine and Barnaby Martin. On the complexity of the model checking problem. CoRR, abs/1210.6893, 2012. Extended abstract appeared at LICS 2011 under the name "A Tetrachotomy for Positive First-Order Logic without Equality". URL: http://arxiv.org/abs/1210.6893.
Barnaby Martin. On the chen conjecture regarding the complexity of qcsps. CoRR, abs/1607.03819, 2016. URL: http://arxiv.org/abs/1607.03819.
Barnaby Martin and Dmitriy Zhuk. Switchability and collapsibility of gap algebras. CoRR, abs/1510.06298, 2015. URL: http://arxiv.org/abs/1510.06298.
Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
R.M. Smullyan. Godel’s Incompleteness Theorems. Oxford Logic Guides. Oxford University Press, 1992. URL: https://books.google.co.uk/books?id=04zalcCdKZsC.
James Wiegold. Growth sequences of finite semigroups. Journal of the Australian Mathematical Society (Series A), 43:16-20, 8 1987. Communicated by H. Lausch. URL: http://dx.doi.org/10.1017/S1446788700028925.
D. Zhuk. The Size of Generating Sets of Powers. ArXiv e-prints, April 2015. URL: http://arxiv.org/abs/1504.02121.