Bounded alternation QCSP on a 3-element domain

Abstract

We consider the complexity of the bounded alternation QCSP, $\Pi_{2k}$-$\mathrm{QCSP}(\Gamma)$ (and $\Sigma_{2k+1}$-$\mathrm{QCSP}(\Gamma)$), as $\Gamma$ ranges over all structures with domain size $3$ and constants. We prove that such problems are always in $\mathsf P$, $\mathsf{NP}$-complete, $\mathsf{coNP}$-complete or $\mathbf{\Pi}{2k}^{\mathsf P}$-complete (or $\mathbf{\Sigma}{2k+1}^{\mathsf P}$-complete, respectively). Since the corresponding problems $\Pi_{2k+1}$-$\mathrm{QCSP}(\Gamma)$ (and $\Sigma_{2k+2}$-$\mathrm{QCSP}(\Gamma)$, respectively) are in $\mathbf{\Pi}{2k}^{\mathsf P}$ (and $\mathbf{\Sigma}{2k+1}^{\mathsf P}$, respectively), our work yields a full classification for all bounded alternation fragments. We borrow heavily from the complexity classification for $\mathrm{QCSP}(\Gamma)$, over all domain size $3$ structures with constants, but the tetrachotomy is not in the same place.