QCSP Monsters and the Demise of the Chen Conjecture
QCSP Monsters and the Demise of the Chen Conjecture
We give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language Γ, QCSP(Γ), where Γ 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 …