Изменения

Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n | \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B \Rightarrow U_B \in \mathrm{NP^B}</tex> (легко написать программу, проверяющую сертификатсертификатом будет слово нужной длины из <tex>B</tex>). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P^B}</tex>.

Рассмотрим последовательность машин Пронумеруем некоторым образом все машины Тьюринга , имеющие доступ к оракулу языка <tex>M_iB</tex>, имеющих доступ к оракулу языка и рассмотрим получившуюся последовательность <tex>BM_i</tex>. Построение множества <tex>B</tex> разделим на счетное число стадий шагов, на каждой из которых множество пополнится конечным числом элементов. Будем строить <tex>B</tex> так, чтобы на <tex>i</tex>-й стадии было выполнено: <tex>T(M_i, x) \ge 2^{|x|-1}</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P^B}</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>следующим образом:** если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на предыдущем шагеодной из предудщих стадий, то она сохраняется;