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

Определение

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

Определение

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

Формулировка теоремы

IP[math][f(n)] = [/math] AM[math][f(n)+ O(1)][/math]

Заметим что, AM[math][f(n)+O(1)] \subset [/math] IP[math][f(n)][/math] для любой функции [math]f[/math], так как открытые монетки "хуже" закрытых.

Докажем теперь, что IP[math][f(n)] \subset [/math] AM[math][f(n)+O(1)][/math]. Для этого докажем, что любой язык [math]L[/math] из IP[math][f(n)][/math] лежит также в AM[math][f(n)+O(1)][/math].

Пусть языку [math]L[/math] соответствует верификатор [math]V'[/math] для которого, в случае, если [math]x \in L[/math], существует прувер [math]P'[/math] такой, что [math]Pr(V'^{P'}(x) = 1) \ge 2/3[/math]. Теперь мы хотим построить верификатор [math]V[/math] из протокола Артура-Мерлина, использующий вероятностную ленту (доступную пруверу [math]P[/math]) и [math]V'[/math].

Рассмотрим множество вероятностных лент [math]R[/math] и его подмножество [math]S \subset R[/math] - множество лент, на которых осуществляется допуск. В соответствии с протоколом, [math]x \in L \Rightarrow P(V(x) = [x \in L]) \ge \frac{2}{3}[/math], т.е. если слово принадлежит языку, то [math]V[/math] должен вывести YES с достаточно большой вероятностью, а если [math]x \notin L[/math], то [math]P(V(x) = [x \in L]) \lt \frac{1}{3}[/math], т.е. если слово не принадлежит языку, то [math]V[/math] разрешено ошибиться, но с достаточно малой вероятностью. Перефразируем эти условия так:

• [math]x \in L \Rightarrow |S|\gt 2K [/math], т.е. если слово принадлежит языку, то множество вероятностных лент, на которых слово будет допущено должно быть достаточно большим;
• [math]x \notin L \Rightarrow |S|\lt K[/math], т.е. если слово не принадлежит языку, то множество вероятностных лент, на которых слово все же будет допущено, должно быть достаточно малым.

Число [math]K[/math] выберем позже.

Cм. также

• Теорема Шамира
• Класс IP