|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
The complete classification for quantified equality constraintsстатья
- Авторы: Zhuk Dmitriy, Martin Barnaby, Wrona Michał
- Сборник: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
- Год издания: 2023
- Издательство: Society for Industrial and Applied Mathematics.
- Местоположение издательства: Philadelphia, United States
- Первая страница: 2746
- Последняя страница: 2760
- DOI: 10.1137/1.9781611977554.ch103
- Аннотация: 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 Γ an equality language. Such problems are either in Logspace, NP-complete, co-NP-complete or rise in complexity in the Polynomial Hierarchy.
- Добавил в систему: Жук Дмитрий Николаевич