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