Изменения

| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.

* Покажем существование такого '''Существование оракула <tex>A</tex>, что ''' Рассмотрим [[PS-полнота языка верных булевых формул с кванторами (TQBF) | PS-полный язык <tex>\mathrm{P^A} = \mathrm{NP^ATQBF} </tex>]]. Рассмотрим язык  <tex> \mathrm{P^{TQBF} = } \overset{(1)}{ \Phi | subseteq}\mathrm{NP^{TQBF}} \overset{(2)}{\Phi subseteq}\--</tex> булева формула с кванторами <tex>, mathrm{NPS^{TQBF}} \Phi overset{(3)}{= 1}\mathrm{PS^{TQBF}} \overset{(4)}</tex>. [[{=}\mathrm{PS-полнота языка верных булевых формул с кванторами } \overset{(TQBF5) | <tex> }{\subseteq}\mathrm{P^{TQBF} }\Rightarrow</tex> является <br/><tex>PS\Rightarrow \mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</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>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_iP_i</tex>. Множество <tex>B</tex> будем строить итеративно, на очередной итерации номер <tex>i</tex> делая так, имеющих доступ к оракулу языка что программа <tex>BP_i</tex>. Построение не распознает множество <tex>BU_B</tex> разделим на счетное число шагов. Будем строить  В начале каждой итерации определимся с тем, с какой длиной слова <tex>Bn_i</tex> так, что на мы будем работать. Для <tex>i-n_i</tex>м шаге выполненодолжны быть выполнены три условия: * <tex>2^{n_i} >T(M_iP_i, x(1) \ge 2^n{n_i})</tex>. Очевидно, что (это утверждение сильнееограничение может быть достигнуто, чем так как мы исследуем только полиномиальные программы)* <tex>U_B \not\in \mathrmn_i > n_{P_Bi-1}</tex>. Начнем поэтапно строить множество (слово должно быть длиннее, чем слово, с которым мы работали на предыдущем шаге)* <tex>n_i > \max\limits_{s \in B} |s|</tex>.** 0-й шаг: , где <tex>B \leftarrow \emptyset </tex>** {{---}} текущая версия множества, которое мы строим (это ограничение может быть достигнуто, так как в множестве <tex>iB</tex>-й шагвсегда конечное число элементов). Будем считать шаги с 0-го по Кроме этого, слово должно быть длиннее, чем все слова, про которые наш оракул раньше ответил, что в множестве <tex>(i-1)B</tex>-й сделаныих нет. Тогда в  Затем запустим программу <tex>BP_i</tex> на данном этапе содержится конечное число слов. Пусть самое длинное из них состоит из слове <tex>(n-1)^n</tex>-го символа. Запустим машину Каждый раз, когда она будет обращаться к оракулу для множества <tex>M_iB</tex> на входе , будем делать следующее:* если запрошенное слово ранее было добавлено в множество <tex>1^nB</tex> на , отвечаем <tex>2^nACCEPT</tex> шагов. Когда * в противном случае отвечаем <tex>M_iREJECT</tex> требуется ответ оракула языка  Если программа отработала и решила, что слово <tex>B(1)^n</tex> о слове принадлежит языку <tex>xU_B</tex>, происходит следующееничего делать не надо:*** Если принадлежность ни одного слова длины <tex>xn</tex> множеству в языке <tex>B</tex> была определена на предыдущем шагенет (из-за третьего требования к длине обрабатываемых слов), то она сохраняетсяи никогда не появится (из-за второго требования к длине обрабатываемых слов).*** Если принадлежность В противном случае, необходимо найти такое слово длины <tex>xn</tex> множеству , о котором программа <tex>BP_i</tex> не установлена ранее, то далее считаем, что спрашивала оракул (оно всегда существует из-за первого требования к длине обрабатываемых слов: программа просто не успела бы спросить обо всех словах длины <tex>x \not\in Bn</tex>.Но ), и добавить это слово в множество <tex>M_iB</tex> могла остановится раньше, чем за . После этого все слова длины <tex>2^n</tex> шагов и вернуть какое-либо значение.*** Если автоматически добавятся в язык <tex>M_iU_B</tex>, то будем считать, что в и программа <tex>BP_i</tex> не содержится слов вида будет верно распознавать этот язык (она будет неверно работать на слове <tex>\{0,(1\})^n</tex>}).