Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/unary-in-p-then-exptime-nexp — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: добавление Категория:Теоретические задачи) |
Bagurgl (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
Докажите, что если каждый [[унарный язык]] из NP также лежит в P, то EXPTIME=NEXP. | Докажите, что если каждый [[унарный язык]] из NP также лежит в P, то EXPTIME=NEXP. | ||
| + | |||
| + | {{reserve-task|[[Участник:Bagurgl|Bagurgl]] 19:50, 14 декабря 2023 (UTC)}} | ||
[[Категория:Нерешенные задачи]] | [[Категория:Нерешенные задачи]] | ||
[[Категория:Теоретические задачи]] | [[Категория:Теоретические задачи]] | ||
Версия 19:50, 14 декабря 2023
Докажите, что если каждый унарный язык из NP также лежит в P, то EXPTIME=NEXP.
Задача зарезервирована: Bagurgl 19:50, 14 декабря 2023 (UTC)