Изменения

<tex>L D \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^LD</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.

Очевидно, что <tex>\mathrm{P} \subset \mathrm{P}^D</tex>.Докажем, что <tex>\mathrm{P}^D \subset \mathrm{P}</tex>. <tex>L \in \mathrm{P}^D \Rightarrow \exists A \in D: L \in \mathrm{P}^A</tex>.появится с минуты на минуту Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время <tex>f(n)</tex> и использующий оракул языка <tex>A</tex>.Пусть <tex>q</tex> {{---}} разрешитель <tex>A</tex>, работающий за полиномиальное время <tex>g(n)</tex>.Представим себе разрешитель <tex>L</tex>, работающий как <tex>p</tex>, но использующий <tex>q</tex> вместо оракула <tex>A</tex>. Его время работы ограничено сверху значением <tex>f(n) + \sum\limits_{i=1}^{f(n)} g(f(n)) = f(n) + f(n) g(f(n))</tex>, что является полиномом. Значит, <tex>L \in \mathrm{P}</tex>.