Изменения

Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.

Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время.<tex> (M \leq L) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \widetilde{P} : w \in M \Leftrightarrow f(w) \in L ) </tex>.Построим разрешитель <tex>q</tex> для языка <tex>M</tex>.появится с минуты на минуту.. <tex>q(w):</tex> if (<tex>p(f(w))</tex>) return true return falseРазрешитель <tex>q</tex> работает за полиномиальное время, так как композиция полиномов есть полином.