Теорема Бейкера — Гилла — Соловэя

Теорема:

Существуют такие оракулы [math]A[/math] и [math]B[/math], что [math]\mathrm{P^A} = \mathrm{NP^A} [/math] и [math]\mathrm{P^B} \ne \mathrm{NP^B} [/math].

Доказательство:

[math]\triangleright[/math]

Существование оракула [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] \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]B[/math] Пусть [math]B[/math] — произвольное множество, а [math]U_B = \{1^n | \exists x \in B : |x| = n\}[/math]. Ясно, что [math]\forall B \Rightarrow U_B \in \mathrm{NP^B}[/math] (легко написать программу, проверяющую сертификат). Построим такое множество [math]B[/math], что [math]U_B \not\in \mathrm{P^B}[/math]. Рассмотрим последовательность машин Тьюринга [math]M_i[/math], имеющих доступ к оракулу языка [math]B[/math]. Построение множества [math]B[/math] разделим на счетное стадий шагов. Будем строить [math]B[/math] так, чтобы на [math]i[/math]-й стадии было выполнено: [math]T(M_i, x) \ge 2^{|x|-1}[/math]. Очевидно, что это утверждение сильнее, чем [math]U_B \not\in \mathrm{P^B}[/math]. 0-я стадия: [math]B \leftarrow \emptyset [/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]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]), а всего слов длины n [math]2^n[/math]. Во множестве [math]B[/math] на каждой стадии содержится конечное число элементов, так как на каждой стадии в [math]B[/math] может быть добавлено не более чем [math]2^{n-1}+1[/math] слов. Рассмотрим построенное по описанному выше алгоритму множество [math]B[/math]. Предположим, что [math]M_i[/math] отработала менее, чем за время [math]2^{n-1}[/math], на слове [math]1^n[/math], где [math]n[/math] определено для каждого [math]i[/math] в алгоритме, описанном выше. Тогда если [math]M_i[/math] допускает слово [math]1^n[/math], то в [math]B[/math] нет слова [math]1^n[/math]; если [math]M_i[/math] отклоняет слово [math]1^n[/math], то в [math]B[/math] содержится слово [math]x[/math], причем [math]|x| = n[/math]. Следовательно, никакая машина [math]M_i[/math] не может решить язык [math]U_B[/math] за время меньшее [math]2^{n-1}[/math].

[math]\triangleleft[/math]