Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/unary-in-p-then-exptime-nexp — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
Строка 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)