The complexity of the Quantified CSP having the polynomially generated powers property

2021/10/18 by Dmitriy Zhuk, Zhuk, Dmitriy
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.2110.09504

openalex publication_date 2021/10/18 · openalex created_date 2021/10/25 · openalex updated_date 2026/07/28

Abstract

It is known that if an algebra of polymorphisms of the constraint language has the Polynomially Generated Powers (PGP) Property then the Quantified CSP can be reduced to the CSP over the same constraint language with constants. The only limitation of this reduction is that it is applicable only for the constraint languages with constants. We drastically simplified the reduction and generalized it for constraint languages without constants. As a result, we completely classified the complexity of the QCSP for constraint languages having the PGP property.

Related

• QCSP monsters and the demise of the Chen Conjecture
• The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation
• The complexity of quantified constraints using the algebraic formulation
• The complete classification for quantified equality constraints
• Proof complexity of CSP