Изменения

Покажем существование такого оракула <tex>B</tex>, что <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>. Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n | \exists x</tex>, что <tex>\in B : |x| = n\}</tex>. Ясно, что <tex>\forall B: \Rightarrow 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 2^{n|x|-1}</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P^B}</tex>. Начнем поэтапно строить множество Построение множества <tex>B</tex>разделим на счетное число шагов.* 0-й шаг: <tex>B \leftarrow \emptyset </tex>.* <tex>i</tex>-й шаг. Будем считать , шаги с 0-го по <tex>(i-1)</tex>-й сделаны. Тогда <tex>B</tex> на данном этапе — конечное множество слов. Пусть самое длинное из них состоит из <tex>(n-1)</tex>-го символа. Запустим машину <tex>M_i</tex> на входе <tex>1^n</tex> на <tex>2^{n-1}</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, будем определять принадлежность этого слова к <tex>B</tex>: