Теорема Голдвассера, Сипсера

Определение

Протокол Артура-Мерлина - интерактивный протокол доказательства, в котором <tex>A<tex>(prover, Arthur) видит вероятностную ленту <tex>M<tex>(verifier, Merlin)(т.н. public coins)

Определение

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

Теорема(Голдвассер, Сипсер)

AM = IP