Интерактивные протоколы. Класс IP. Класс AM

Класс IP

Определение:

[math]IP[f] = \{L|\exists \langle V, P \rangle : [/math] [math] 1) \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} [/math] [math] 2) \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} [/math] [math] 3) [/math] Число раундов интерактивного протокола [math] 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]