Изменения

Перейти к: навигация, поиск

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

6 байт убрано, 00:03, 17 апреля 2012
Нет описания правки
** <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>
** <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>
Анонимный участник

Навигация