Изменения

==Определение=='''Протокол Артура-Мерлина''' - [[Класс IP|интерактивный протокол доказательства]], в котором прувер <tex>P</tex>(prover, Merlin) видит вероятностную ленту верифайера. <tex>V</tex>(verifier, Arthur)(''т.н. public coins'')

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