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

Теорема:

Существуют такие оракулы [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], что [math]\mathrm{P^A} = \mathrm{NP^A} [/math]. Рассмотрим язык [math] \mathrm{TQBF} = \{ \Phi | \Phi \--[/math] булева формула с кванторами [math], \Phi = 1\}[/math]. [math] \mathrm{TQBF} [/math] является [math]PS[/math]-полным языком. [math] \mathrm{P} \subset \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subset \mathrm{NP^{TQBF}} [/math] [math]T(p,x) \ge S(p, x)[/math], для любых [math]p, x \Rightarrow \mathrm{NP^{TQBF}} \subset \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} \-- \mathrm{PS}[/math]-полная [math]\Rightarrow \mathrm{PS} \in \mathrm{P^{TQBF}}[/math] Следовательно, [math]\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}[/math] Покажем существование такого оракула [math]B[/math], что [math]\mathrm{P^B} \ne \mathrm{NP^B} [/math]. Пусть [math]B\--[/math] произвольное множество, а [math]U_B = \{1^n | \exists x[/math], что [math]|x| = n\}[/math]. Ясно, что [math]\forall B: 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 \frac{2^n}{10}[/math]

[math]\triangleleft[/math]