|
|
| Строка 10: |
Строка 10: |
| | | | |
| | Заметим что, '''AM'''<tex>[f(n)+O(1)] \subset </tex> '''IP'''<tex>[f(n)]</tex> для любой функции <tex>f</tex>, так как открытые монетки "хуже" закрытых. | | Заметим что, '''AM'''<tex>[f(n)+O(1)] \subset </tex> '''IP'''<tex>[f(n)]</tex> для любой функции <tex>f</tex>, так как открытые монетки "хуже" закрытых. |
| − |
| |
| − | Докажем теперь, что '''IP'''<tex>[f(n)] \subset </tex> '''AM'''<tex>[f(n)+O(1)]</tex>.
| |
| − | Для этого докажем, что любой язык <tex>L</tex> из '''IP'''<tex>[f(n)]</tex> лежит также в '''AM'''<tex>[f(n)+O(1)]</tex>.
| |
| − |
| |
| − | Пусть языку <tex>L</tex> соответствует верификатор <tex>V'</tex> для которого, в случае, если <tex>x \in L</tex>, существует прувер <tex>P'</tex> такой, что <tex>Pr(V'^{P'}(x) = 1) \ge 2/3</tex>.
| |
| − | Теперь мы хотим построить верификатор <tex>V</tex> из протокола Артура-Мерлина, использующий вероятностную ленту (доступную пруверу <tex>P</tex>) и <tex>V'</tex>.
| |
| − |
| |
| − |
| |
| − | Рассмотрим множество вероятностных лент <tex>R</tex> и его подмножество <tex>S \subset R</tex> - множество лент, на которых осуществляется допуск. В соответствии с протоколом, <tex>x \in L \Rightarrow P(V(x) = [x \in L]) \ge \frac{2}{3}</tex>, т.е. если слово принадлежит языку, то <tex>V</tex> должен вывести YES с достаточно большой вероятностью, а если <tex>x \notin L</tex>, то <tex>P(V(x) = [x \in L]) < \frac{1}{3}</tex>, т.е. если слово не принадлежит языку, то <tex>V</tex> разрешено ошибиться, но с достаточно малой вероятностью. Перефразируем эти условия так:
| |
| − | * <tex>x \in L \Rightarrow |S|>2K </tex>, т.е. если слово принадлежит языку, то множество вероятностных лент, на которых слово будет допущено должно быть достаточно большим;
| |
| − | * <tex>x \notin L \Rightarrow |S|<K</tex>, т.е. если слово не принадлежит языку, то множество вероятностных лент, на которых слово все же будет допущено, должно быть достаточно малым.
| |
| − | Число <tex>K</tex> выберем позже.
| |
| − |
| |
| − | ==Cм. также==
| |
| − | *[[Теорема Шамира]]
| |
| − | *[[Класс IP]]
| |
Версия 13:30, 9 июня 2010
Определение
Протокол Артура-Мерлина - интерактивный протокол доказательства, в котором [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], так как открытые монетки "хуже" закрытых.
