QCSP Monsters and the Demise of the Chen Conjecture
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
QCSP Monsters and the Demise of the Chen Conjecture
Popis výsledku v původním jazyce
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)
Název v anglickém jazyce
QCSP Monsters and the Demise of the Chen Conjecture
Popis výsledku anglicky
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)
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
—
Návaznosti
R - Projekt Ramcoveho programu EK
Ostatní
Rok uplatnění
2022
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Journal of the ACM
ISSN
0004-5411
e-ISSN
1557-735X
Svazek periodika
69
Číslo periodika v rámci svazku
5
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
44
Strana od-do
35
Kód UT WoS článku
000885828900005
EID výsledku v databázi Scopus
2-s2.0-85086769591