Временная и пространственная сложность алгоритмов/Задачи/dtime-n2-is-closed-carp-reduction — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «* Класс сложности ''С'' замкнут относительно какой-то сводимости, если L→L' и <m>L' \in C</m>, то <m>L…») |
StasFomin (обсуждение | вклад) (Массовая правка: добавление Категория:Теоретические задачи) |
||
| Строка 5: | Строка 5: | ||
[[Категория:Нерешенные задачи]] | [[Категория:Нерешенные задачи]] | ||
| + | [[Категория:Теоретические задачи]] | ||
Текущая версия на 06:51, 4 мая 2023
- Класс сложности С замкнут относительно какой-то сводимости, если L→L' и , то .
Рассмотрим класс .
Замкнут ли он относительно полиномиальной сводимости по Карпу?