![]() |
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
We prove that QCSP(N;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 Γ an equality language. Such problems are either in Logspace, NP-complete, co-NP-complete or rise in complexity in the Polynomial Hierarchy.