Изменения

# Так как <tex>S(p,x) \le T(p, x)</tex>, то <tex> \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \subseteq \mathrm{NPS^{TQBF}} </tex>.

Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n \bigm| \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B \Rightarrow </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>B</tex>, и рассмотрим получим последовательность <tex>M_iP_i</tex>, в которой каждая машина Тьюринга встречается бесконечное число раз. Очевидно, это можно сделать в силу счетности множества машин Тьюринга. Построение множества Множество <tex>B</tex> разделим на счетное число стадий, на каждой из которых множество пополнится конечным числом элементов. Будем будем строить <tex>B</tex> такитеративно, чтобы на очередной итерации номер <tex>i</tex>-й стадии было выполнено: существует слово <tex>x</tex>делая так, что программа <tex>T(M_i, x) \ge 2^{n-1}P_i</tex>. Это утверждение сильнее, чем не распознает множество <tex>U_B \not\in \mathrm{P}^B</tex>, так как <tex>2^n</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-1}</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, будем определять принадлежность этого слова к <tex>B</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-1}n_i</tex> шагов и вернуть какое-либо значениемы будем работать. Так как Для <tex>Bn_i</tex> строится с условием, что для выбранного должны быть выполнены три условия:* <tex>x = 12^n</tex> выполнено: <tex{n_i} >T(M_iP_i,x(1) \ge 2^{n-1n_i})</tex>(это ограничение может быть достигнуто, то решение машины о принадлежности слова должно быть неверным:так как мы исследуем только полиномиальные программы)* если <tex>M_i</tex> приняла слово, то исключим из <tex>B</tex> все слова вида <texn_i >\n_{0,i-1\}^n</tex>;* Если <tex>M_i</tex> отклонила (словодолжно быть длиннее, то выберем чем слово , с которым мы работали на предыдущем шаге)* <tex>x</texn_i > длины <tex>n\max\limits_{s \in B} |s|</tex>, принадлежность которого где <tex>B</tex> еще не определено. Добавим <tex>x</tex> {{---}} текущая версия множества, которое мы строим (это ограничение может быть достигнуто, так как в множестве <tex>B</tex>всегда конечное число элементов). Такое Кроме этого, слово всегда найдетсядолжно быть длиннее, чем все слова, так как на предыдущий шагах мы могли сделать не болеепро которые наш оракул раньше ответил, чем <tex>2^n-1</tex> запросов к оракулу (то есть определить принадлежность что в множестве <tex>B</tex> не более <tex>2^n-1</tex> слов длины <tex>n</tex>), а всего слов длины n <tex>2^n</tex>их нет.

Во множестве Затем запустим программу <tex>P_i</tex> на слове <tex>(1)^n</tex>. Каждый раз, когда она будет обращаться к оракулу для множества <tex>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии будем делать следующее:* если запрошенное слово ранее было добавлено в множество <tex>B</tex> может быть добавлено не более чем , отвечаем <tex>ACCEPT</tex>* в противном случае отвечаем <tex>2^{n-1}+1REJECT</tex> слов.

Из построения получаемЕсли программа отработала и решила, что для любой машины Тьюринга слово <tex>M(1)^n</tex> существует бесконечно много слов из принадлежит языку <tex>U_B</tex>, для которых <tex>M</tex> ничего делать не может принять верное решение о принадлежности надо: ни одного слова длины <tex>U_B</tex> за время, меньшее <tex>2^{n-1}</tex>. Следовательно, в языке <tex>U_B \not\in \mathrm{P}^B</tex>нет (из-за третьего требования к длине обрабатываемых слов), и никогда не появится (из-за второго требования к длине обрабатываемых слов).

==СледствияСледствие==

| statement = Методом диагонализации нельзя доказать, что Если существует решение вопроса равенства <tex>\mathrm{P} \neq </tex> и <tex> \mathrm{NP}</tex>, то оно не должно «релятивизоваться».

{{ Утверждение| statement = Если существует решение вопроса равенства Для доказательства строгого включения классов часто используется метод диагонализации. Однако утверждения, полученные при помощи данной техники, могут быть «релятивизованы». То есть при «разрешении» машине Тьюринга доступа к оракулу некоторого языка доказанное соотношение классов сохраняется. Однако соотношение <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно "релятивизоваться", поэтому стандартные техники«релятивизоваться» по теореме Бейкера-Гилла-Соловэя, напримерследовательно, диагонализация метод диагонализации не применимаприменим для решения этого вопроса.}}