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