The Complexity of Quantified Constraints Using the Algebraic Formulation

DOI10.4230/LIPICS.MFCS.2017.27zbMATH Open1441.68087arXiv1701.04086OpenAlexW2963678585MaRDI QIDQ5111241FDOQ5111241

Author name not available (Why is that?)

Publication date: 26 May 2020

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 QCSP(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.

Full work available at URL: https://arxiv.org/abs/1701.04086

zbMATH Keywords

computational complexityconstraint satisfactionuniversal algebraquantified constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity classifications of Boolean constraint satisfaction problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• The Complexity of General-Valued CSPs
• The complexity of equality constraint languages
• The complexity of constraint satisfaction games and QCSP
• Quantified Equality Constraints
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• Quantified constraint satisfaction and the polynomially generated powers property
• The size of generating sets of powers
• Meditations on Quantified Constraint Satisfaction
• From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP
• The Complexity of Positive First-Order Logic without Equality

Cited In (6)

• Title not available (Why is that?)
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
• The size of generating sets of powers
• The algebraic structure of the densification and the sparsification tasks for CSPs
• The complexity of problems for quantified constraints
• Constraint satisfaction problem: what makes the problem easy

This page was built for publication: The Complexity of Quantified Constraints Using the Algebraic Formulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111241)