Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/unary-in-p-then-exptime-nexp — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «Докажите, что если каждый унарный язык из NP также лежит в P, то EXPTIME=NEXP. Категория:Нереш…») |
StasFomin (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
Докажите, что если каждый [[унарный язык]] из NP также лежит в P, то EXPTIME=NEXP. | Докажите, что если каждый [[унарный язык]] из NP также лежит в P, то EXPTIME=NEXP. | ||
| − | [[Категория: | + | [[Категория:Решенные задачи]] |
| + | [[Категория:Теоретические задачи]] | ||
Текущая версия на 06:53, 18 декабря 2023
Докажите, что если каждый унарный язык из NP также лежит в P, то EXPTIME=NEXP.