Класс IP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Доказательство)
Строка 15: Строка 15:
 
<tex>NP \subset IP[1] </tex>, <tex>BPP \subset IP[0] </tex>
 
<tex>NP \subset IP[1] </tex>, <tex>BPP \subset IP[0] </tex>
 
==Доказательство==
 
==Доказательство==
Первое утверждение верно, так как определить, принадлежит ли слово языку можно за один запрос. <tex>V</tex> посылает запрос к <tex>P</tex> и в ответ либо получает сертификат (если слово принадлежит языку), либо не получает (если слово не принадлежит языку).
+
Первое утверждение верно, так как определить, принадлежит ли слово языку можно за один запрос. <tex>V</tex> посылает запрос к <tex>P</tex> и в ответ либо получает сертификат, если слово принадлежит языку, либо не получает, если слово не принадлежит языку (<tex>V</tex> хочет убедить <tex>P</tex>, когда слово принадлежит, поэтому пришлет сертификат в случае его существования).
  
 
Второе утверждение очевидно, так как для проверки принадлежности к [[Сложностный класс BPP|BPP]] хватает вычислительной мощности <tex>V</tex>, и запросов к <tex>V</tex> делать не нужно.
 
Второе утверждение очевидно, так как для проверки принадлежности к [[Сложностный класс BPP|BPP]] хватает вычислительной мощности <tex>V</tex>, и запросов к <tex>V</tex> делать не нужно.

Версия 16:01, 6 мая 2010

Определение

Интерактивный протокол доказательства - абстрактная машина, модулирующая вычисление как передачу сообщений между двумя сущностями: [math]P[/math] - prover и [math]V[/math] - verifier. В ходе данного взаимодействия [math]P[/math] и [math]V[/math] определяют, принадлежит ли данное слово [math]x[/math] языку. [math]P[/math] имеет неограниченную вычислительную мощность и пытается доказать, что [math]x[/math] принадлежит языку. [math]V[/math] - вероятностная машина Тьюринга, работающая за полином и проверяющая информацию от [math]P[/math]. При этом [math]P[/math] не видит вероятностную ленту [math]V[/math]. [math]V[/math] хочет допустить слово тогда и только тогда, когда оно принадлежит языку.

Определение

Классом [math]IP[f(n)][/math] (IP = interactive proof) называется множество языков, распознаваемых с помощью интерактивного протокола доказательства. При этом:

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

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

3) количество обращений к [math]P \le f(n) [/math]

Теорема

[math]NP \subset IP[1] [/math], [math]BPP \subset IP[0] [/math]

Доказательство

Первое утверждение верно, так как определить, принадлежит ли слово языку можно за один запрос. [math]V[/math] посылает запрос к [math]P[/math] и в ответ либо получает сертификат, если слово принадлежит языку, либо не получает, если слово не принадлежит языку ([math]V[/math] хочет убедить [math]P[/math], когда слово принадлежит, поэтому пришлет сертификат в случае его существования).

Второе утверждение очевидно, так как для проверки принадлежности к BPP хватает вычислительной мощности [math]V[/math], и запросов к [math]V[/math] делать не нужно.

Определение

[math]I = IP[poly][/math] - класс языков, распознаваемых с помощью интерактивного протокола доказательства с полиномиальным числом запросов от [math]V[/math] к [math]P[/math].