Изменения
→Теорема
==Теорема==
{{ Теорема
# <tex> \mathrm{P} \subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subseteq \mathrm{NP^{TQBF}} </tex>.
# Так как <tex>S(p,x) \le T(p, x)</tex>, то <tex> \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \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{PSC} \Rightarrow \mathrm{PS} \subseteq \mathrm{P^{TQBF}} </tex>.
Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>
----
'''Существование оракула <tex>B</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>Bi</tex> делая так, чтобы на что программа <tex>i</tex>-й стадии было выполнено: <tex>M_iP_i</tex> не распознает язык <tex>U_B</tex> за время не большее, чем <tex>2^{n-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>x</tex> множеству <tex>B</tex> была определена на одной из предудщих стадий, то она сохраняется;** если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.
В противном случае, необходимо найти такое слово длины <tex>n</tex>, о котором программа <tex>P_i</tex> не спрашивала оракул (оно всегда существует из-за первого требования к длине обрабатываемых слов: программа просто не успела бы спросить обо всех словах длины <tex>n</tex>), и добавить это слово в множество <tex>B</tex>. После этого все слова длины <tex>n</tex> автоматически добавятся в язык <tex>U_B</tex>, и программа <tex>P_i</tex> не будет верно распознавать этот язык (она будет неверно работать на слове <tex>(1)^n</tex>).
}}
==СледствияСледствие==
{{ Утверждение
| statement = Методом диагонализации нельзя доказать, что Если существует решение вопроса равенства <tex>\mathrm{P} \neq </tex> и <tex> \mathrm{NP}</tex>, то оно не должно «релятивизоваться».
}}
