#### The complete classification for quantified equality constraints

##### Dmitriy Zhuk, Barnaby Martin

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 quantified equality languages as a trichotomy between Logspace, NP-complete and PSpace-complete.

arrow_drop_up