Теорема Голдвассера, Сипсера
Определение
Протокол Артура-Мерлина - интерактивный протокол доказательства, в котором (prover, Merlin) видит вероятностную ленту (verifier, Arthur)(т.н. public coins)
Определение
- класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов к не превышает .
Формулировка теоремы
План доказательства
Рассмотрим множество вероятностных лент
и его подмножество - множество лент, на которых осуществляется допуск. Если для некоторого множества и числа выполняется , то допустим слово.Доказательство
Итак, есть множество теореме) и . Далее, отправим запрос на получение , такого, что , и проверим, верно ли в действительности, что полученный . Пусть .
, и мы хотим доказать, что либо , либо . Выберем так, чтобы . Возьмем ( существует согласно соответствующей- если , то успех .
- если , и , то поступим следующим образом. Мы хотим, чтобы выполнялось:
. Рассмотрим .