Изменения
Нет описания правки
** <tex> \mathrm{TQBF} \-- \mathrm{PS}</tex>-полная <tex>\Rightarrow \mathrm{PS} \in \mathrm{P^{TQBF}}</tex>
Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>
* Покажем существование такого оракула <tex>B</tex>, что <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.Пусть <tex>B\--</tex> произвольное множество, а <tex>U_B = \{1^n | \exists x</tex>, что <tex>|x| = n\}</tex>. Ясно, что <tex>\forall B: U_B \in \mathrm{NP^B}</tex> (легко написать программу, проверяющую сертификат). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P^B}</tex>.Рассмотрим последовательность машин Тьюринга <tex>M_i</tex>, имеющих доступ к оракулу языка <tex>B</tex>. Построение множество <tex>B</tex> разделим на счетное число шагов. Будем строить <tex>B</tex> так, что на <tex>i-</tex>м шаге выполнено: <tex>T(M_i, x) \ge \frac{2^n}{10}</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P_B}</tex>. Начнем поэтапно строить множество <tex>B</tex>.** 0-й шаг: <tex>B \leftarrow \emptyset </tex>** <tex>i</tex>-й шаг.
}}
