# The complete classification for quantified equality constraints

arXiv: https://arxiv.org/abs/2104.00406 · HTML: https://mlsanity.com/paper/2104.00406/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Apr 2021.

## Built on by (most cited first, 1 of 1)

- [On Classifying Continuous Constraint Satisfaction Problems](https://mlsanity.com/paper/2106.02397/) (2021)

## Abstract (arXiv)

We prove that QCSP(mathbbN;x=yrightarrow 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(Gamma), for Gamma an equality language. Such problems are either in Logspace, NP-complete, co-NP-complete or rise in complexity in the Polynomial Hierarchy.