Изменения

Заметим, что в таком случае класс языков <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>