Изменения
Нет описания правки
==Определение==
'''Протокол Артура-Мерлина''' - [[Класс IP|интерактивный протокол доказательства]], в котором <tex>AP</tex>(prover, ArthurMerlin) видит вероятностную ленту <tex>MV</tex>(verifier, MerlinArthur)(''т.н. public coins'')
==Определение==
<tex>AM[f(n)]</tex> - класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов <tex>AV</tex> к <tex>MP</tex> не превышает <tex>f(n)</tex>.
==Теорема(Голдвассер, Сипсер)==
==План доказательства==
Рассмотрим множество вероятностных лент <tex>R</tex> и его подмножество <tex>S \subset R</tex> - множество лент, на которых осуществляется допуск. Если для некоторого множества <tex>S</tex> и числа <tex>k</tex> выполняется <tex>|S| > 2K</tex>, то допустим слово.
==Доказательство==
Итак, есть множество <tex>S \subset 2^{m}</tex>, и мы хотим доказать, что либо <tex>|S| > 2K</tex>, либо <tex>|S| < K</tex>.
Мы умеем определять, верно ли, что <tex>s \in S</tex>.
Выберем <tex>k</tex> так, чтобы <tex>2^{k-2} \le 2K \le 2^{k-1}</tex>.
Далее, <tex>h in H_{m,k}</tex>; <tex>y \in 2^k</tex>. Отправляем запрос <tex>P</tex> на получение <tex>s \ in S</tex>:
<tex>h(s) = y</tex>, и проверяем, верно ли в действительности, что <tex>s \ in S</tex>.
