Теорема Бейкера — Гилла — Соловэя — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
** <tex>T(p,x) \ge S(p, x)</tex>, для любых <tex>p, x \Rightarrow \mathrm{NP^{TQBF}} \subset \mathrm{NPS^{TQBF}}</tex>
 
** <tex>T(p,x) \ge S(p, x)</tex>, для любых <tex>p, x \Rightarrow \mathrm{NP^{TQBF}} \subset \mathrm{NPS^{TQBF}}</tex>
 
** По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex>
 
** По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex>
**
+
** <tex> \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = <tex> \mathrm{PS} </tex>
 +
** <tex> \mathrm{TQBF} \-- \mathrm{PS}</tex>-полная <tex>\Rightarrow \mathrm{PS} \in \mathrm{P^{TQBF}}</tex>
 +
Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>
 +
* Покажем существование такого оракула <tex>B</tex>, что <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.
 +
 
 
}}
 
}}

Версия 01:05, 16 апреля 2012

Теорема:
Существуют такие оракулы [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}} = \lt tex\gt \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]\triangleleft[/math]