Изменения
Нет описания правки
----
'''Существование оракула <tex>B</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 2^n</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</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, происходит следующее:
