The complexity of quantified constraints using the algebraic formulation

DOI10.4230/LIPICS.MFCS.2017.27MaRDI QIDQ5111241zbMATH OpenOpenAlexFDO

Authors

Publication date 26 May 2020

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)

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.

Recommendations

• Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
• Quantified constraint satisfaction and the polynomially generated powers property
• From complexity to algebra and back: digraph classes, collapsibility, and the PGP
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• Quantified constraint satisfaction problem on semicomplete digraphs

Cites work

• scientific article; zbMATH DE number 4008678 (Why is no real title available?)
• scientific article; zbMATH DE number 53543 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Classifying the Complexity of Constraints Using Finite Algebras
• Complexity classifications of Boolean constraint satisfaction problems
• From complexity to algebra and back: digraph classes, collapsibility, and the PGP
• Meditations on quantified constraint satisfaction
• Quantified Equality Constraints
• Quantified constraint satisfaction and the polynomially generated powers property
• Quantified constraint satisfaction on monoids
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of constraint satisfaction games and QCSP
• The complexity of equality constraint languages
• The complexity of general-valued CSPs
• The complexity of positive first-order logic without equality
• The size of generating sets of powers

Cited in

(10)

• scientific article; zbMATH DE number 1343490 (Why is no real title available?)
• The complexity of problems for quantified constraints
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
• From complexity to algebra and back: digraph classes, collapsibility, and the PGP
• QCSP Monsters and the Demise of the Chen Conjecture
• The size of generating sets of powers
• The algebraic structure of the densification and the sparsification tasks for CSPs
• Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
• Constraint satisfaction problem: what makes the problem easy
• Quantified constraint satisfaction and the polynomially generated powers property

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)