51
правка
Изменения
→Определение
==Определение==
Язык <mathtex>A\,\!</mathtex> сводится по Карпу к языку <mathtex>B\,\!</mathtex>, если существует функция <mathtex>f(x)\,\!</mathtex> такая, что <mathtex>x \in A</mathtex> тогда и только тогда, когда <mathtex>f(x) \in bB</mathtex>.
Обычно требуют, чтобы сводящая функция была вычислима за полиномиальное время от длины входа.
Заметим, что в таком случае класс языков P замкнут относительно сведения по Карпу, т.к. сводящая функция может решить сводимую задачу за полиномиальное время от длины входа и выдать нужный результат.
==Пример==
