Bounded alternation QCSP on a 3-element domain

Zhuk, Dmitriy, Carvalho, Catarina and Martin, Barnaby (2026) Bounded alternation QCSP on a 3-element domain. ZML: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik., 72. pp. 473-486.
Copy

We consider the complexity of the bounded alternation QCSP, Π2k-QCSP(Γ) (andΣ2k+1-QCSP(Γ)), as Γ ranges over all structures with domain size 3 and constants. We prove thatsuch problems are always in P, NP-complete, coNP-complete or ΠP2k-complete (or ΣP2k+1-complete,respectively). Since the corresponding problems Π2k+1-QCSP(Γ) (and Σ2k+2-QCSP(Γ), respectively)are in ΠP2k (and ΣP2k+1, respectively), our work yields a full classification for all bounded alternationfragments. We borrow heavily from the complexity classification for QCSP(Γ), over all domain size 3structures with constants, but the tetrachotomy is not in the same place


picture_as_pdf
CAM.328-ZhukCarvalhoMartin-2026.pdf
subject
Published Version
Available under Creative Commons: BY 4.0

View Download

EndNote BibTeX Reference Manager Refer Atom Dublin Core Data Cite XML HTML Citation MODS OpenURL ContextObject RIOXX2 XML METS OpenURL ContextObject in Span OPENAIRE MPEG-21 DIDL ASCII Citation
Export

Downloads