Изменения

'''Существование оракула <tex>A</tex>.'''

Покажем существование такого оракула Рассмотрим [[PS-полнота языка верных булевых формул с кванторами (TQBF) | PS-полный язык <tex>A\mathrm{TQBF}</tex>, что ]]. <tex>\mathrm{P^A{TQBF}} = \overset{(1)}{\subseteq}\mathrm{NP^A{TQBF} </tex>. Рассмотрим язык <tex> } \overset{(2)}{\subseteq}\mathrm{NPS^{TQBF}} \overset{(3)}{=}\mathrm{PS^{TQBF} } \overset{(4)}{= }\mathrm{PS} \overset{(5)}{ \Phi | subseteq}\Phi mathrm{P^{TQBF}}\--Rightarrow</tex> булева формула с кванторами <br/><tex>, \Phi = 1Rightarrow \mathrm{P^{TQBF}</tex>. [[PS-полнота языка верных булевых формул с кванторами (TQBF) | <tex> } = \mathrm{NP^{TQBF}} </tex> является <tex>PS</tex>-полным языком]].*# <tex> \mathrm{P} \subset subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subset subseteq \mathrm{NP^{TQBF}} </tex>.* # Так как <tex>TS(p,x) \ge Sle T(p, x)</tex>, для любых то <tex>p, x \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \subset subseteq \mathrm{NPS^{TQBF}}</tex>.* # По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex>.* # <tex> \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} </tex>.* # <tex> \mathrm{TQBF} \-- in \mathrm{PSPSC}</tex>-полный <tex>\Rightarrow \mathrm{PS} \in subseteq \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 \bigm| \exists x</tex>, что <tex>\in B : |x| = n\}</tex>. Ясно, что <tex>\forall B: </tex> выполнено <tex>U_B \in \mathrm{NP}^B}</tex> (легко написать программу, проверяющую сертификатсертификатом будет слово нужной длины из <tex>B</tex>). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P}^B}</tex>. Рассмотрим  Пронумеруем полиномиальные программы, получим последовательность машин Тьюринга <tex>M_i</tex>, имеющих доступ к оракулу языка <tex>BP_i</tex>. Построение множество Множество <tex>B</tex> разделим будем строить итеративно, на счетное число шагов. Будем строить очередной итерации номер <tex>Bi</tex> делая так, что на программа <tex>i-P_i</tex>м шаге выполнено: не распознает множество <tex>T(M_i, x) \ge 2^nU_B</tex>. Очевидно В начале каждой итерации определимся с тем, что это утверждение сильнее, чем с какой длиной слова <tex>U_B \not\in \mathrm{P_B}n_i</tex>мы будем работать. Начнем поэтапно строить множество Для <tex>Bn_i</tex>.должны быть выполнены три условия:* 0-й шаг: <tex>B \leftarrow \emptyset 2^{n_i} > T(P_i, (1)^{n_i})</tex>(это ограничение может быть достигнуто, так как мы исследуем только полиномиальные программы)* <tex>n_i > n_{i-1}</tex>-й шаг. Будем считать шаги (слово должно быть длиннее, чем слово, с 0-го по которым мы работали на предыдущем шаге)* <tex>(i-1)n_i > \max\limits_{s \in B} |s|</tex>-й сделаны. Тогда в , где <tex>B</tex> на данном этапе содержится конечное число слов. Пусть самое длинное из них состоит из {{---}} текущая версия множества, которое мы строим (это ограничение может быть достигнуто, так как в множестве <tex>(n-1)B</tex>-го символавсегда конечное число элементов). Запустим машину Кроме этого, слово должно быть длиннее, чем все слова, про которые наш оракул раньше ответил, что в множестве <tex>M_iB</tex> на входе их нет. Затем запустим программу <tex>1^nP_i</tex> на слове <tex>2(1)^n</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка Каждый раз, когда она будет обращаться к оракулу для множества <tex>B</tex> о слове <tex>x</tex>, происходит будем делать следующее:** Если принадлежность если запрошенное слово ранее было добавлено в множество <tex>xB</tex> множеству , отвечаем <tex>BACCEPT</tex> была определена на предыдущем шаге, то она сохраняется.** Если принадлежность в противном случае отвечаем <tex>xREJECT</tex> множеству  Если программа отработала и решила, что слово <tex>B(1)^n</tex> не установлена ранее, то далее считаем, что принадлежит языку <tex>x \not\in BU_B</tex>.Но , ничего делать не надо: ни одного слова длины <tex>M_in</tex> могла остановится раньше, чем за в языке <tex>2^nB</tex> шагов нет (из-за третьего требования к длине обрабатываемых слов), и вернуть какоеникогда не появится (из-либо значениеза второго требования к длине обрабатываемых слов).* Если В противном случае, необходимо найти такое слово длины <tex>M_in</tex> приняла слово, то будем считать, что в о котором программа <tex>BP_i</tex> не содержится спрашивала оракул (оно всегда существует из-за первого требования к длине обрабатываемых слов вида : программа просто не успела бы спросить обо всех словах длины <tex>\{0,1\}^n</tex>}.* Если ), и добавить это слово в множество <tex>M_iB</tex> отклонила слово, то выберем слово . После этого все слова длины <tex>xn</tex> длины автоматически добавятся в язык <tex>nU_B</tex>, принадлежность которого и программа <tex>BP_i</tex> еще не определено. Тогда будет верно распознавать этот язык (она будет неверно работать на слове <tex>x \in B(1)^n</tex>).}} ==Следствие==

Если <tex>M_i</tex> допускает слово <tex>1^n</tex>, то в <tex>B</tex> нет слова <tex>1^n</tex>. {{ Утверждение| statement = Если существует решение вопроса равенства <tex>M_i\mathrm{P}</tex> отклоняет слово и <tex>1^n\mathrm{NP}</tex>, то в <tex>B</tex> содержится слово <tex>x</tex>, причем <tex>|x| = n</tex>. Противоречие.Следовательно, <tex>M_i</tex> оно не может решить язык <tex>U_B</tex> за время меньшее <tex>2^n</tex>должно «релятивизоваться».