The complete classification for quantified equality constraints
This settles a long-standing open question in computational complexity for quantified constraint satisfaction over equality languages, providing a complete classification for the community.
The paper proves that QCSP(ℕ; x=y → y=z) is PSpace-complete, resolving a decade-old open problem and completing the complexity classification for quantified equality constraints as a trichotomy (Logspace, NP-complete, PSpace-complete). It also classifies bounded alternation variants, showing they are either in Logspace, NP-complete, co-NP-complete, or higher in the Polynomial Hierarchy.
We prove that QCSP$(\mathbb{N};x=y\rightarrow y=z)$ is PSpace-complete, settling a question open for more than ten years. This completes the complexity classification for the QCSP over equality languages as a trichotomy between Logspace, NP-complete and PSpace-complete. We additionally settle the classification for bounded alternation QCSP$(Γ)$, for $Γ$ an equality language. Such problems are either in Logspace, NP-complete, co-NP-complete or rise in complexity in the Polynomial Hierarchy.