Изменения
→Доказательство
==Доказательство==
Заметим что, очевидно, '''AM'''<tex>[f(n)+O(1)] \subset </tex>'''IP'''<tex>[f(n)], \forall f</tex>. Докажем теперь, что '''IP'''<tex>[f(n)] \subset </tex>'''AM'''<tex>[f(n)+O(1)]</tex>
Рассмотрим множество вероятностных лент <tex>R</tex> и его подмножество <tex>S \subset R</tex> - множество лент, на которых осуществляется допуск. В соответствии с протоколом, <tex>x \in L \Rightarrow P(V(x) = [x \in L]) \ge \frac{2}{3}</tex>, т.е. если слово принадлежит языку, то <tex>V</tex> должен вывести YES с достаточно большой вероятностью, а если <tex>x \notin L</tex>, то <tex>P(V(x) = [x \in L]) < \frac{1}{3}</tex>, т.е. если слово не принадлежит языку, то <tex>V</tex> разрешено ошибиться, но с достаточно малой вероятностью. Перефразируем эти условия так:
Запустим построенный протокол доказательства некоторое константное количество раз для того, чтобы повысить точность, а именно добиться того, чтобы было:
* <tex>x \notin L \Rightarrow P(V(x) = [x \in L]) < \frac{1}{3}</tex>
Итак, '''IP'''<tex>[f(n)] \subset </tex>'''AM'''<tex>[f(n)+O(1)]</tex>. Теорема доказана.
==Cм. также==
*[[Теорема Шамира]]
*[[Класс IP]]
