Класс IP
| Определение: |
Интерактивным протоколом называется абстрактная машина, моделирующая вычисления как обмен сообщениями между двумя программами ([math]Prover[/math] и [math]Verifier[/math]), такими, что
- [math]Prover[/math] убеждает [math]Verifier[/math] в том, что слово [math]x[/math] принадлежит языку
- [math]Prover[/math] не ограничен в вычислительной мощности
- [math]Verifier[/math] — вероятностная машина Тьюринга
- [math]Verifier[/math] ограничен полиномиальным временем работы
|
Далее [math]Prover[/math] обозначается [math]P[/math], а [math]Verifier[/math] — [math]V[/math].
Интерактивные протоколы делятся на два типа в зависимости от доступа [math]P[/math] к вероятностной ленте [math]V[/math] (см. рис. 1).
| Определение: |
[math]IP[f] = \{L|\exists \langle V, P \rangle : [/math]
- [math] \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} [/math]
- [math] \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} [/math]
- число раундов интерактивного протокола [math] O(f(n)), n = |x| [/math]
|
| Теорема: |
[math]\mathrm{BPP} \subset \mathrm{IP[0]}[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Это очевидным образом следует из определений [math]\mathrm{BPP}[/math] и [math]V[/math] в [math]\mathrm{IP}[/math]; [math]V[/math] даже не требуется общаться с [math]P[/math]. |
| [math]\triangleleft[/math] |
| Теорема: |
[math]\mathrm{NP} \subset \mathrm{IP[1]}[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math]V[/math] будет проверять на принадлежность слова [math]x[/math] используя сертификат, который он запросит у [math]P[/math]. Так как [math]P[/math] неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы [math]V[/math] принял слово. Для этого требуется лишь один раунд интерактивного протокола, что и доказывает теорему. |
| [math]\triangleleft[/math] |
