Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/unary-in-p-then-time2kn-in-time2cn — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «Докажите, что если каждый унарный язык из NP также лежит в P, то то для любого языка из <m>T…») |
StasFomin (обсуждение | вклад) (Массовая правка: добавление Категория:Теоретические задачи) |
||
| Строка 3: | Строка 3: | ||
[[Категория:Нерешенные задачи]] | [[Категория:Нерешенные задачи]] | ||
| + | [[Категория:Теоретические задачи]] | ||
Текущая версия на 06:51, 4 мая 2023
Докажите, что если каждый унарный язык из NP также лежит в P, то то для любого языка из для какого-либо k, он тажке лежит в для любого c.