Document Open Access Logo

The Complexity of Quantified Constraints Using the Algebraic Formulation

Authors Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.27.pdf
  • Filesize: 478 kB
  • 14 pages

Document Identifiers

Author Details

Catarina Carvalho
Barnaby Martin
Dmitriy Zhuk

Cite As Get 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.

Subject Classification

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

  1. Manuel Bodirsky and Hubie Chen. Quantified equality constraints. SIAM J. Comput., 39(8):3682-3699, 2010. URL: http://dx.doi.org/10.1137/080725209.
  2. 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. Google Scholar
  3. 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.
  4. A. Bulatov, A. Krokhin, and P. G. Jeavons. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34:720-742, 2005. Google Scholar
  5. 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. Google Scholar
  6. 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.
  7. 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.
  8. 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.
  9. Hubie Chen and Peter Mayr. Quantified constraint satisfaction on monoids, 2016. Google Scholar
  10. Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications 7, 2001. Google Scholar
  11. 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. Google Scholar
  12. 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. Google Scholar
  13. 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.
  14. 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.
  15. Barnaby Martin. On the chen conjecture regarding the complexity of qcsps. CoRR, abs/1607.03819, 2016. URL: http://arxiv.org/abs/1607.03819.
  16. Barnaby Martin and Dmitriy Zhuk. Switchability and collapsibility of gap algebras. CoRR, abs/1510.06298, 2015. URL: http://arxiv.org/abs/1510.06298.
  17. Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  18. R.M. Smullyan. Godel’s Incompleteness Theorems. Oxford Logic Guides. Oxford University Press, 1992. URL: https://books.google.co.uk/books?id=04zalcCdKZsC.
  19. 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.
  20. D. Zhuk. The Size of Generating Sets of Powers. ArXiv e-prints, April 2015. URL: http://arxiv.org/abs/1504.02121.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact