Изменения

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