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.
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
| Item Type | Article |
|---|---|
| Identification Number | 10.60866/CAM.328 |
| Additional information | © 2026 The Authors. This article is licensed under the Creative Commons BY 4.0 license. https://creativecommons.org/licenses/by/4.0/ |
| Date Deposited | 19 Nov 2026 16:30 |
| Last Modified | 21 Nov 2026 02:01 |
