==Теорема==
{{ Теорема
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.
| proof =
==='''Существование оракула <tex>A</tex>===''' Покажем существование такого оракула Рассмотрим [[PS-полнота языка верных булевых формул с кванторами (TQBF) | PS-полный язык <tex>A\mathrm{TQBF}</tex>, что ]]. <tex>\mathrm{P^A{TQBF}} \overset{(1)}{\subseteq} = \mathrm{NP^A{TQBF}} \overset{(2)}{\subseteq}\mathrm{NPS^{TQBF}} \overset{(3)}{=} </tex>. Рассмотрим язык <tex> \mathrm{PS^{TQBF} } \overset{(4)}{= }\mathrm{ PS} \Phi | overset{(5)}{\Phi subseteq}\--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>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>, происходит следующее:
** Если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на предыдущем шаге, то она сохраняется.
** Если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.
Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^n</tex> шагов и вернуть какое-либо значение.
* Если <tex>M_i</tex> приняла слово, то будем считать, что в <tex>B</tex> не содержится слов вида <tex>\{0,1\}^n</tex>}.
* Если <tex>M_i</tex> отклонила слово, то выберем слово <tex>x</tex> длины <tex>n</tex>, принадлежность которого <tex>B</tex> еще не определено. Тогда <tex>x \in B</tex>.
Если ---- '''Существование оракула <tex>B</tex>''' Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n \bigm| \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B</tex> выполнено <tex>M_iU_B \in \mathrm{NP}^B</tex> допускает (сертификатом будет слово нужной длины из <tex>B</tex>). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P}^B</tex>. Пронумеруем полиномиальные программы, получим последовательность <tex>P_i</tex>. Множество <tex>B</tex> будем строить итеративно, на очередной итерации номер <tex>i</tex> делая так, что программа <tex>P_i</tex> не распознает множество <tex>U_B</tex>. В начале каждой итерации определимся с тем, с какой длиной слова <tex>n_i</tex> мы будем работать. Для <tex>n_i</tex> должны быть выполнены три условия:* <tex>2^{n_i} > T(P_i, (1)^n{n_i})</tex> (это ограничение может быть достигнуто, так как мы исследуем только полиномиальные программы)* <tex>n_i > n_{i-1}</tex> (слово должно быть длиннее, чем слово, с которым мы работали на предыдущем шаге)* <tex>n_i > \max\limits_{s \in B} |s|</tex>, где <tex>B</tex> {{---}} текущая версия множества, которое мы строим (это ограничение может быть достигнуто, так как в множестве <tex>B</tex>всегда конечное число элементов). Кроме этого, слово должно быть длиннее, чем все слова, про которые наш оракул раньше ответил, то что в множестве <tex>B</tex> их нет слова . Затем запустим программу <tex>P_i</tex> на слове <tex>(1)^n</tex>. Каждый раз, когда она будет обращаться к оракулу для множества <tex>B</tex>, будем делать следующее:Если * если запрошенное слово ранее было добавлено в множество <tex>B</tex>, отвечаем <tex>ACCEPT</tex>* в противном случае отвечаем <tex>M_iREJECT</tex> отклоняет Если программа отработала и решила, что слово <tex>(1)^n</tex> принадлежит языку <tex>U_B</tex>, то ничего делать не надо: ни одного слова длины <tex>n</tex> в языке <tex>B</tex> содержится нет (из-за третьего требования к длине обрабатываемых слов), и никогда не появится (из-за второго требования к длине обрабатываемых слов). В противном случае, необходимо найти такое слово длины <tex>xn</tex>, причем о котором программа <tex>P_i</tex> не спрашивала оракул (оно всегда существует из-за первого требования к длине обрабатываемых слов: программа просто не успела бы спросить обо всех словах длины <tex>|x| = n</tex>), и добавить это слово в множество <tex>B</tex>. Противоречие.Следовательно, После этого все слова длины <tex>M_in</tex> не может решить автоматически добавятся в язык <tex>U_B</tex> за время меньшее , и программа <tex>P_i</tex> не будет верно распознавать этот язык (она будет неверно работать на слове <tex>2(1)^n</tex>).}} ==Следствие== {{ Утверждение| statement = Если существует решение вопроса равенства <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно «релятивизоваться».
}}
Для доказательства строгого включения классов часто используется метод диагонализации. Однако утверждения, полученные при помощи данной техники, могут быть «релятивизованы». То есть при «разрешении» машине Тьюринга доступа к оракулу некоторого языка доказанное соотношение классов сохраняется. Однако соотношение <tex>\mathrm{P}</tex> и <tex>\mathrm{NP}</tex> не должно «релятивизоваться» по теореме Бейкера-Гилла-Соловэя, следовательно, метод диагонализации не применим для решения этого вопроса.
[[Категория: Теория сложности]]
