Изменения

# Так как <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>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_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>M_iP_i</tex>, имеющих доступ к оракулу языка <tex>B</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 </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>xB</tex> множеству , отвечаем <tex>BACCEPT</tex> была определена на предыдущем шаге, то она сохраняется;** если принадлежность в противном случае отвечаем <tex>xREJECT</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.

Но <tex>M_i</tex> могла остановится раньшеЕсли программа отработала и решила, чем за что слово <tex>2^{n-(1}</tex> шагов и вернуть какое-либо значение. Так как <tex>B</tex> строится с условием <tex>T(M_i, x) \ge 2^{n-1}</tex>, то решение машины о принадлежности слова должно быть неверным:* если принадлежит языку <tex>M_iU_B</tex> приняла слово, то исключим из <tex>B</tex> все ничего делать не надо: ни одного слова вида <tex>\{0,1\}^n</tex>;* Если <tex>M_i</tex> отклонила слово, то выберем слово <tex>x</tex> длины <tex>n</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>n</tex>, о котором программа <tex>P_i</tex> не спрашивала оракул (оно всегда существует из-за первого требования к длине обрабатываемых слов: программа просто не успела бы спросить обо всех словах длины <tex>Bn</tex> на каждой стадии содержится конечное число элементов), так как на каждой стадии и добавить это слово в множество <tex>B</tex> может быть добавлено . После этого все слова длины <tex>n</tex> автоматически добавятся в язык <tex>U_B</tex>, и программа <tex>P_i</tex> не более чем будет верно распознавать этот язык (она будет неверно работать на слове <tex>2(1)^{n-1}+1</tex> слов).}}

Рассмотрим построенное по описанному выше алгоритму множество <tex>B</tex>. Предположим, что <tex>M_i</tex> отработала менее, чем за время <tex>2^{n-1}</tex>, на слове <tex>1^n</tex>, где <tex>n</tex> определено для каждого <tex>i</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>.=Следствие==

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