Бюрократы, editor, Администраторы
422
правки
Изменения
м
Тире в техе
'''Существование оракула <tex>A</tex>.'''
Покажем существование такого оракула <tex>A</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex>. Рассмотрим язык <tex> \mathrm{TQBF} = \{ \Phi | \Phi \--</tex> — булева формула с кванторами <tex>, \Phi = 1\}</tex>. [[PS-полнота языка верных булевых формул с кванторами (TQBF) | <tex> \mathrm{TQBF} </tex> является <tex>PS</tex>-полным языком]].
*<tex> \mathrm{P} \subset \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subset \mathrm{NP^{TQBF}} </tex>.
* <tex>T(p,x) \ge S(p, x)</tex>, для любых <tex>p, x \Rightarrow \mathrm{NP^{TQBF}} \subset \mathrm{NPS^{TQBF}}</tex>.
