Abstrakt
We give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language Gamma, QCSP(Gamma), where Gamma is a finite language over three elements that contains all constants. In particular, such problems are in P, NP-complete, co-NP-complete, or PSpace-complete.
Our classification refutes the hitherto widely believed Chen Conjecture. Additionally, we show that already on a 4-element domain there exists a constraint language Gamma such that QCSP(Gamma) is DP-complete (from Boolean Hierarchy), and on a 10-element domain there exists a constraint language giving the complexity class Theta(P)(2).
Meanwhile, we prove the Chen Conjecture for finite conservative languages Gamma. If the polymorphism clone of such Gamma has the polynomially generated powers property, then QCSP(Gamma) is in NP.
Otherwise, the polymorphism clone of Gamma has the exponentially generated powers property and QCSP(Gamma) is PSpace-complete.(1)