Интерактивные протоколы. Класс IP. Класс AM — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Класс IP== {{Определение |definition = <tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> <br/> <tex> 1) \forall x \in L \Rightarrow P(V(x) ...»)
 
Строка 6: Строка 6:
 
<tex> 2) \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex><br/>
 
<tex> 2) \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex><br/>
 
<tex> 3) </tex> Число раундов интерактивного протокола <tex> f(n), n = |x| </tex><br/>
 
<tex> 3) </tex> Число раундов интерактивного протокола <tex> f(n), n = |x| </tex><br/>
 +
}}
 +
 +
{{Теорема
 +
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
 +
|proof=
 +
Это очевидным образом следует из определений <tex>\mathrm{BPP}</tex> и <tex>V</tex> в <tex>\mathrm{IP}</tex>; <tex>V</tex> даже не требуется общаться с <tex>P</tex>.
 
}}
 
}}
  
Строка 11: Строка 17:
 
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
 
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
 
|proof=
 
|proof=
−
*<tex>\mathrm{NC^i} \subset \mathrm{AC^i}</tex> <br/>
+
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола, что и доказывает теорему.
−
Это понятно из определения <tex>\mathrm{NC^i}</tex> и <tex>\mathrm{AC^i}</tex>. <br/>
 
−
*<tex>\mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex> <br/>
 
−
Пусть <tex>L \in \mathrm{AC^i}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Значит, степень входа элементов схемы <tex>C_n</tex> — это полином от <tex>n</tex>. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более двух следующим образом: <br/>
 
−
[[Файл:circuit.jpg]]
 
−
При замене каждого такого элемента глубина схемы увеличивается не более чем в <tex>log_2 r(n) = O(log(n))</tex>, а так как изначально глубина схемы была <tex>O(log^i(n))</tex>, то после замены всех элементов глубина схемы станет <tex>O(log^i(n)) \cdot O(log(n)) = O(log^{i+1}(n))</tex>.<br> Так как при замене элемента мы добавляем не более <tex>r(n)</tex> элементов, а изначально размер схемы был полиномиальным и каждый ее элемент мы заменили на полином элементов, то после всех замен размер схемы остался полиномиальным.
 
 
}}
 
}}

Версия 19:47, 26 мая 2012

Класс IP

Определение:
[math]IP[f] = \{L|\exists \langle V, P \rangle : [/math]

[math] 1) \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} [/math]
[math] 2) \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} [/math]

[math] 3) [/math] Число раундов интерактивного протокола [math] f(n), n = |x| [/math]


Теорема:
[math]\mathrm{BPP} \subset \mathrm{IP[0]}[/math]
Доказательство:
[math]\triangleright[/math]
Это очевидным образом следует из определений [math]\mathrm{BPP}[/math] и [math]V[/math] в [math]\mathrm{IP}[/math]; [math]V[/math] даже не требуется общаться с [math]P[/math].
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{NP} \subset \mathrm{IP[1]}[/math]
Доказательство:
[math]\triangleright[/math]
[math]V[/math] будет проверять на принадлежность слова [math]x[/math] используя сертификат, который он запросит у [math]P[/math]. Так как [math]P[/math] неограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы [math]V[/math] принял слово. Для этого требуется лишь один раунд интерактивного протокола, что и доказывает теорему.
[math]\triangleleft[/math]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Интерактивные_протоколы._Класс_IP._Класс_AM&oldid=22781»