The complete classification for quantified equality constraints
The complete classification for quantified equality constraints
We prove that QCSP(ℕ; x = y → 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 …