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

Определение

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

Определение

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

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

AM = IP