|
|
| (не показано 59 промежуточных версий 3 участников) |
| Строка 3: |
Строка 3: |
| | | | |
| | ==Определение== | | ==Определение== |
| − | <tex>AM[f(n)]</tex> - класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов <tex>V</tex> к <tex>P</tex> не превышает <tex>f(n)</tex>. | + | '''AM'''<tex>[f(n)]</tex> - класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов <tex>V</tex> к <tex>P</tex> не превышает <tex>f(n)</tex>. |
| | | | |
| − | ==Теорема(Голдвассер, Сипсер)== | + | ==Формулировка теоремы== |
| − | <tex>IP[f(n)] = AM[f(n)+2]</tex> | + | '''[[Класс IP|IP]]'''<tex>[f(n)] = </tex> '''AM'''<tex>[f(n)+ O(1)]</tex> |
| | | | |
| − | ==План доказательства==
| |
| − | Рассмотрим множество вероятностных лент <tex>R</tex> и его подмножество <tex>S \subset R</tex> - множество лент, на которых осуществляется допуск. Если для некоторого множества <tex>S</tex> и числа <tex>k</tex> выполняется <tex>|S| > 2K</tex>, то допустим слово.
| |
| | | | |
| − | ==Доказательство==
| + | Заметим что, '''AM'''<tex>[f(n)+O(1)] \subset </tex> '''IP'''<tex>[f(n)]</tex> для любой функции <tex>f</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>.
| + | Правильное напишем в следующем году. |
| − | Пусть <tex>p=\frac{2K}{2^k}</tex>.
| + | То, что было правильно из этого доказательства, перенесено в статью [[Протокол Гольдвассера-Сипсера для оценки размера множества]] |
| − | * если <tex>|S|<K</tex> , то <tex>|h(s)| < \frac{p \cdot 2^k}{2} = K \Rightarrow P(</tex>успех<tex>) \le p/2</tex>.
| |
| − | * если <tex>|S|>2K</tex>, и <tex>|S|<2^{k-1}</tex>, то поступим следующим образом. Мы хотим, чтобы выполнялось:
| |
| − | <tex>P_{h,y}(\exists s: h(s)=y) \ge \frac{3}{4} \cdot \frac{|s|}{2K}</tex>
| |
| − | Рассмотрим <tex>y \in 2^m</tex>. <tex>P_{h}(\exists s: h(s)=y) = P_{h}(y \in \bigcup \limits_{s}h(s))=P_{h}(\bigcup \limits_{s}E_s) \ge \sum_{j}P(E_s)-\sum \limits_{s_1 \ne s_2}P(E_{s_1} \bigcap E_{s_2})= \frac{|s|}{2^k}-\frac{1}{2}|s|^{2}\frac{1}{2^{2k}}=|s|\frac{1}{2^k}\left ( 1 - \frac{|s|}{2^{k+1}} \right ) > \frac{3}{4}p</tex>
| |
Определение
Протокол Артура-Мерлина - интерактивный протокол доказательства, в котором [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], так как открытые монетки "хуже" закрытых.
Тут было неправильное доказательство теоремы.
Правильное напишем в следующем году.
То, что было правильно из этого доказательства, перенесено в статью Протокол Гольдвассера-Сипсера для оценки размера множества
