Изменения

'''Протокол Артура-Мерлина''' - [[Класс IP|интерактивный протокол доказательства]], в котором <tex>AP</tex>(prover, ArthurMerlin) видит вероятностную ленту <tex>MV</tex>(verifier, MerlinArthur)(''т.н. public coins'')

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

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

==План доказательства==Рассмотрим множество вероятностных лент <tex>RЗаметим что, '''AM'''</tex> и его подмножество <tex>S [f(n)+O(1)] \subset R</tex> - множество лент, на которых осуществляется допуск. Если для некоторого множества '''IP'''<tex>S[f(n)]</tex> и числа для любой функции <tex>k</tex> выполняется <tex>|S| > 2Kf</tex>, то допустим словотак как открытые монетки "хуже" закрытых.  ----Тут было неправильное доказательство теоремы.Правильное напишем в следующем году.То, что было правильно из этого доказательства, перенесено в статью [[Протокол Гольдвассера-Сипсера для оценки размера множества]]