Изменения

'''AM'''<tex>AM[f(n)]</tex> - класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов <tex>V</tex> к <tex>P</tex> не превышает <tex>f(n)</tex>.

==Теорема(Голдвассер, Сипсер)Формулировка теоремы=='''[[Класс IP|IP]]'''<tex>IP[f(n)] = </tex> '''AM'''<tex>[f(n)+2O(1)]</tex>

==Доказательство==ИтакЗаметим что, есть множество '''AM'''<tex>S [f(n)+O(1)] \subset 2^{m}</tex>, и мы хотим доказать, что либо '''IP'''<tex>|S| > 2K[f(n)]</tex>, либо для любой функции <tex>|S| < Kf</tex>, так как открытые монетки "хуже" закрытых.Мы умеем определять, верно ли, что <tex>s \in S</tex>.Выберем <tex>k</tex> так, чтобы <tex>2^{k---2} \le 2K \le 2^{k-1}</tex>Тут было неправильное доказательство теоремы.Далее, <tex>h \in H_{m,k}</tex>; <tex>y \in 2^k</tex>Правильное напишем в следующем году. Отправляем запрос <tex>P</tex> на получение <tex>s \in S</tex>: <tex>h(s) = y</tex>То, и проверяемчто было правильно из этого доказательства, верно ли перенесено в действительности, что <tex>s \in S</tex>.Пусть <tex>p = \frac{2K}{2^k}</tex>.* если <tex>|S| < K </tex> , то <tex>|h(s)| < \frac{p \cdot 2^k}{2} = K P(\mbox{успех}) \le p/2</tex>.статью [[Протокол Гольдвассера-Сипсера для оценки размера множества]]