Теорема Бейкера — Гилла — Соловэя — различия между версиями
Строка 2: | Строка 2: | ||
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex> | | statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex> | ||
| proof = | | proof = | ||
− | * Покажем существование такого оракула <tex>A</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex>. Рассмотрим язык <tex> \mathrm{TQBF} = \{ \Phi | \Phi \--</tex> булева формула с кванторами <tex>, \Phi = 1\}</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>-полным языком]]. |
}} | }} |