Теорема Бейкера — Гилла — Соловэя — различия между версиями
(Новая страница: «{{ Теорема | statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <t...») |
|||
| Строка 1: | Строка 1: | ||
{{ Теорема | {{ Теорема | ||
| 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 = | ||
| + | * Покажем существование такого оракула <tex>A</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex>. Рассмотрим язык <tex> \mathrm{TQBF} = \{ \Phi | \Phi \--</tex> булева формула с кванторами <tex>, \Phi = 1\}</tex> | ||
}} | }} | ||
Версия 22:00, 15 апреля 2012
| Теорема: |
Существуют такие оракулы и , что и |
| Доказательство: |
|
