Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/unary-in-p-then-time2kn-in-time2cn — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «Докажите, что если каждый унарный язык из NP также лежит в P, то то для любого языка из <m>T…») |
|||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
Докажите, что если каждый [[унарный язык]] из NP также лежит в P, то | Докажите, что если каждый [[унарный язык]] из NP также лежит в P, то | ||
то для любого языка из <m>TIME(2^{kn})</m> для какого-либо k, он тажке лежит в <m>TIME(2^{cn})</m> для любого ''c''. | то для любого языка из <m>TIME(2^{kn})</m> для какого-либо k, он тажке лежит в <m>TIME(2^{cn})</m> для любого ''c''. | ||
| + | {{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 23:51, 19 декабря 2024 (UTC)}} | ||
[[Категория:Нерешенные задачи]] | [[Категория:Нерешенные задачи]] | ||
| + | [[Категория:Теоретические задачи]] | ||
Текущая версия на 23:51, 19 декабря 2024
Докажите, что если каждый унарный язык из NP также лежит в P, то то для любого языка из для какого-либо k, он тажке лежит в для любого c.
Задача зарезервирована: Nikitashapovalov 23:51, 19 декабря 2024 (UTC)