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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment