QCSP Monsters and the Demise of the Chen Conjecture

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10453397" target="_blank" >RIV/00216208:11320/22:10453397 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Aboakfu9rw" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Aboakfu9rw</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3563820" target="_blank" >10.1145/3563820</a>

Result language
angličtina
Original language name
QCSP Monsters and the Demise of the Chen Conjecture
Original language description
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)
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)