211
правок
Изменения
м
→Соотношения с другими классами теории сложности
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP}[0]</tex>.
|proof=
<tex>V\mathit{Verifier}</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P\mathit{Prover}</tex>.
}}
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V\mathit{Verifier}</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P\mathit{Prover}</tex>. Так как <tex>P\mathit{Prover}</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V\mathit{Verifier}</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}
