Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/unary-in-p-then-time2kn-in-time2cn — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (тотальный сброс резервирования) |
|||
| Строка 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''. | ||
| − | + | ||
[[Категория:Нерешенные задачи]] | [[Категория:Нерешенные задачи]] | ||
[[Категория:Теоретические задачи]] | [[Категория:Теоретические задачи]] | ||
Текущая версия на 12:58, 25 сентября 2025
Докажите, что если каждый унарный язык из NP также лежит в P, то то для любого языка из для какого-либо k, он тажке лежит в для любого c.