Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/unary-in-p-then-exptime-nexp
Материал из DISCOPAL
< Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC | Задачи
Версия от 19:50, 14 декабря 2023; Bagurgl (обсуждение | вклад)
Докажите, что если каждый унарный язык из NP также лежит в P, то EXPTIME=NEXP.
Задача зарезервирована: Bagurgl 19:50, 14 декабря 2023 (UTC)
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.