51
правка
Изменения
→Определение
Обычно требуют, чтобы сводящая функция была вычислима за полиномиальное время от длины входа.
Заметим, что в таком случае класс языков <tex>P </tex> замкнут относительно сведения по Карпу, т.к. сводящая функция может решить сводимую задачу за полиномиальное время от длины входа и выдать нужный результат.
==Пример==
