|
Существование оракула [math]A[/math]
Рассмотрим PS-полный язык [math]\mathrm{TQBF}[/math].
[math]
\mathrm{P^{TQBF}} \overset{(1)}{\subseteq}
\mathrm{NP^{TQBF}} \overset{(2)}{\subseteq}
\mathrm{NPS^{TQBF}} \overset{(3)}{=}
\mathrm{PS^{TQBF}} \overset{(4)}{=}
\mathrm{PS} \overset{(5)}{\subseteq}
\mathrm{P^{TQBF}}
\Rightarrow
[/math]
[math]\Rightarrow \mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}[/math].
- [math] \mathrm{P} \subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subseteq \mathrm{NP^{TQBF}} [/math].
- Так как [math]S(p,x) \le T(p, x)[/math], то [math] \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \subseteq \mathrm{NPS^{TQBF}} [/math].
- По теореме Сэвича [math] \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} [/math].
- [math] \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} [/math].
- [math] \mathrm{TQBF} \in \mathrm{PSC} \Rightarrow \mathrm{PS} \subseteq \mathrm{P^{TQBF}} [/math].
Следовательно, [math]\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}[/math]
Существование оракула [math]B[/math]
Пусть [math]B[/math] — произвольное множество, а [math]U_B = \{1^n \bigm| \exists x \in B : |x| = n\}[/math]. Ясно, что [math]\forall B[/math] выполнено [math]U_B \in \mathrm{NP}^B[/math] (сертификатом будет слово нужной длины из [math]B[/math]). Построим такое множество [math]B[/math], что [math]U_B \not\in \mathrm{P}^B[/math].
Пронумеруем некоторым образом все машины Тьюринга, работающие за полиномиальное время и имеющие доступ к оракулу языка [math]B[/math], и рассмотрим последовательность [math]M_i[/math], в которой каждая машина Тьюринга встречается бесконечное число раз. Очевидно, это можно сделать в силу счетности множества машин Тьюринга. Построение множества [math]B[/math] разделим на счетное число стадий. Будем строить [math]B[/math] так, чтобы на [math]i[/math]-й стадии было выполнено: существует слово [math]x[/math], что [math]T(M_i, x) \ge 2^{n-1}[/math]. Это утверждение сильнее, чем [math]U_B \not\in \mathrm{P}^B[/math], так как [math]2^n[/math] растет быстрее любого полинома.
- 0-я стадия: [math]B \leftarrow \varnothing [/math].
- [math]i[/math]-я стадия. Стадии с 0-й по [math](i-1)[/math]-ю пройдены, [math]B[/math] — конечное множество слов. Пусть самое длинное из них состоит из [math](n-1)[/math]-го символа. Запустим машину [math]M_i[/math] на входе [math]1^n[/math] на [math]2^{n-1}[/math] шагов. Когда [math]M_i[/math] требуется ответ оракула языка [math]B[/math] о слове [math]x[/math], будем определять принадлежность этого слова к [math]B[/math] следующим образом:
- если принадлежность [math]x[/math] множеству [math]B[/math] была определена на одной из предыдущих стадий, то она сохраняется;
- если принадлежность [math]x[/math] множеству [math]B[/math] не установлена ранее, то далее считаем, что [math]x \not\in B[/math].
Но [math]M_i[/math] могла остановиться раньше, чем за [math]2^{n-1}[/math] шагов, и вернуть какое-либо значение. Так как [math]B[/math] строится с условием, что для выбранного [math]x = 1^n[/math] выполнено: [math]T(M_i,x) \ge 2^{n-1}[/math], то решение машины о принадлежности слова должно быть неверным:
- если [math]M_i[/math] приняла слово, то исключим из [math]B[/math] все слова вида [math]\{0,1\}^n[/math];
- Если [math]M_i[/math] отклонила слово, то выберем слово [math]x[/math] длины [math]n[/math], принадлежность которого [math]B[/math] еще не определена. Добавим [math]x[/math] в [math]B[/math]. Такое слово всегда найдется, так как на предыдущих шагах мы могли сделать не более, чем [math]2^n-1[/math] запросов к оракулу (то есть определить принадлежность [math]B[/math] не более [math]2^n-1[/math] слов длины [math]n[/math]), а всего слов длины [math]n[/math] [math]2^n[/math].
Во множестве [math]B[/math] на каждой стадии содержится конечное число элементов, так как на каждой стадии в [math]B[/math] может быть добавлено не более чем [math]2^{n-1}+1[/math] слов.
Из построения получаем, что для любой машины Тьюринга [math]M[/math] существует бесконечно много слов из [math]U_B[/math], для которых [math]M[/math] не может принять верное решение о принадлежности слова [math]U_B[/math] за время, меньшее [math]2^{n-1}[/math]. Следовательно, [math]U_B \not\in \mathrm{P}^B[/math]. |
