Изменения

Перейти к: навигация, поиск

Сведение по Карпу

1 байт добавлено, 14:00, 19 марта 2010
Определение
Обычно требуют, чтобы сводящая функция была вычислима за полиномиальное время от длины входа.
Заметим, что в таком случае класс языков <tex>P</tex> замкнут относительно сведения по Карпу. Если язык <tex>L</tex> не равен пустому языку и не равен <tex>\Sigma ^*</tex>, то существуют слова <tex>x_1 \in L</tex> и <tex>x_2 \not\in L</tex>. Сводящая функция <tex>f(x)</tex> может решить сводимую задачу <tex>M</tex> за полиномиальное время от длины входа и выдать <tex>x_1</tex>, если <tex>x \in M</tex>, или <tex>x_2</tex>, если <tex>x \not\in M</tex>
==Пример==
51
правка

Навигация