Теорема
| Теорема: |
Существуют такие оракулы [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]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]M_i[/math]. Множество [math]B[/math] будем строить итеративно, на очередной итерации номер [math]i[/math] делая так, что программа [math]M_i[/math] не распознает множество [math]U_B[/math].
В начале каждой итерации определимся с тем, с какой длиной слова [math]n[/math] мы будем работать. Для [math]n[/math] должны быть выполнены два условия:
- [math]2^n \gt T(M_i, (1)^1[/math] (это ограничение может быть достигнуто, так как мы исследуем только полиномиальные программы)
- [math]n \gt \max_{s \in B} |s|}[/math] (это ограничение может быть достигнуто, так как в множестве [math]B[/math] всегда конечное количество элементов)
|
| [math]\triangleleft[/math] |
Следствие
| Утверждение: |
Если существует решение вопроса равенства [math]\mathrm{P}[/math] и [math] \mathrm{NP}[/math], то оно не должно «релятивизоваться». |
Для доказательства строгого включения классов часто используется метод диагонализации. Однако утверждения, полученные при помощи данной техники, могут быть «релятивизованы». То есть при «разрешении» машине Тьюринга доступа к оракулу некоторого языка доказанное соотношение классов сохраняется. Однако соотношение [math]\mathrm{P}[/math] и [math]\mathrm{NP}[/math] не должно «релятивизоваться» по теореме Бейкера-Гилла-Соловэя, следовательно, метод диагонализации не применим для решения этого вопроса.
