Изменения

# Так как <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>M_i</tex>, имеющих доступ к оракулу языка <tex>BP_i</tex>. Построение множества Множество <tex>B</tex> разделим на счетное стадий шагов. Будем будем строить <tex>B</tex> такитеративно, чтобы на очередной итерации номер <tex>i</tex>-й стадии было выполнено: <tex>T(M_i, x) \ge 2^{|x|-1}</tex>. Очевидноделая так, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P^B}программа </tex>.* 0-я стадия: <tex>B \leftarrow \emptyset P_i</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 BU_B</tex>.

Но <tex>M_i</tex> могла остановится раньшеВ начале каждой итерации определимся с тем, чем за с какой длиной слова <tex>2^{n-1}n_i</tex> шагов и вернуть какое-либо значениемы будем работать. Так как Для <tex>Bn_i</tex> строится с условием должны быть выполнены три условия:* <tex>2^{n_i} >T(M_iP_i, x(1) \ge 2^{n-1n_i})</tex>(это ограничение может быть достигнуто, то решение машины о принадлежности слова должно быть неверным:так как мы исследуем только полиномиальные программы)* если <tex>M_i</tex> приняла слово, то исключим из <texn_i >B</tex> все слова вида <tex>\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>B</tex>. ПредположимЕсли программа отработала и решила, что слово <tex>M_i</tex> отработала менее, чем за время <tex>2^{n-1}</tex>, на слове <tex>(1)^n</tex>, где <tex>n</tex> определено для каждого принадлежит языку <tex>iU_B</tex> в алгоритме, описанном выше. Тогда *если <tex>M_i</tex> допускает слово ничего делать не надо: ни одного слова длины <tex>1^n</tex>, то в языке <tex>B</tex> нет слова <tex>1^n</tex>;*если <tex>M_i</tex> отклоняет слово <tex>1^n</tex>(из-за третьего требования к длине обрабатываемых слов), то в <tex>B</tex> содержится слово <tex>x</tex>, причем <tex>|x| = n</tex>и никогда не появится (из-за второго требования к длине обрабатываемых слов).

СледовательноВ противном случае, никакая машина необходимо найти такое слово длины <tex>M_in</tex> , о котором программа <tex>P_i</tex> не спрашивала оракул (оно всегда существует из-за первого требования к длине обрабатываемых слов: программа просто не может решить успела бы спросить обо всех словах длины <tex>n</tex>), и добавить это слово в множество <tex>B</tex>. После этого все слова длины <tex>n</tex> автоматически добавятся в язык <tex>U_B</tex> за время меньшее , и программа <tex>P_i</tex> не будет верно распознавать этот язык (она будет неверно работать на слове <tex>2(1)^{n-1}</tex>).

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

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

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