141
правка
Изменения
м
→Свойства класса P: + mathrm
|proof =
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время.
<tex> (M \leq L) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \mathrm{\widetilde{P}} : w \in M \Leftrightarrow f(w) \in L ) </tex>.
Построим разрешитель <tex>q</tex> для языка <tex>M</tex>.
<tex>q(w):</tex>
