Изменения

Перейти к: навигация, поиск

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

2 байта добавлено, 15:30, 20 мая 2010
Доказательство
* если <tex>|S|>2^{k-1}</tex>, то <tex>V</tex> примет слово с вероятностью, большей, чем <tex>\frac{3}{4}</tex>.
Теперь, выберем <tex>K</tex>: <tex>K = \frac{1}{3}2^{P(|x|)}</tex>.
Запустим построенный протокол доказательства некоторое константное количество раз для того, чтобы повысить точность, а именно добиться того, чтобы было: <tex>x \notin L \Rightarrow P(V(x) = [x \in L]) < \frac{1}{3}</tex>. 
Итак, '''IP'''<tex>[f(n)] \subset </tex> '''AM'''<tex>[f(n)+O(1)]</tex>. Теорема доказана.
Анонимный участник

Навигация