Временная и пространственная сложность алгоритмов/Задачи/dtime-n2-is-closed-carp-reduction — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «* Класс сложности ''С'' замкнут относительно какой-то сводимости, если L→L' и <m>L' \in C</m>, то <m>L…»)
(нет различий)

Версия 00:31, 4 марта 2021

  • Класс сложности С замкнут относительно какой-то сводимости, если L→L' и , то .

Рассмотрим класс .

Замкнут ли он относительно полиномиальной сводимости по Карпу?