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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
м (rollbackEdits.php mass rollback)
 
(не показано 56 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
==Определение==
 
==Определение==
Классом <tex>IP[f(n)]</tex> (IP = interactive proof) называется множество языков, распознаваемых с помощью интрактивного протокола доказательства. Интрерактивный протокол доказательства - алгоритм, описывающий процесс передачи информации между двумя вычислительными машинами: <tex>P</tex> - prover и <tex>V</tex> - verifier. <tex>P</tex> пытается доказать, что данная строка <tex>x</tex> принадлежит языку. <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]],
+
'''Интерактивный протокол доказательства''' - абстрактная машина, модулирующая вычисление как передачу сообщений между двумя сущностями: <tex>P</tex> - prover и <tex>V</tex> - verifier. В ходе данного взаимодействия <tex>P</tex> и <tex>V</tex> определяют, принадлежит ли данное слово <tex>x</tex> языку. <tex>P</tex> имеет неограниченную вычислительную мощность и пытается доказать, что <tex>x</tex> принадлежит языку. <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]],
работающая за полином и проверяющая информацию от <tex>P</tex> (<tex>P</tex> не видит вероятностную ленту <tex>V</tex>). <tex>V</tex> хочет допустить слово тогда, и только тогда, когда оно принадлежит языку. При этом:
+
работающая за полином и проверяющая информацию от <tex>P</tex>. При этом <tex>P</tex> не видит вероятностную ленту <tex>V</tex>. <tex>V</tex> хочет допустить слово тогда и только тогда, когда оно принадлежит языку.
  
1) <tex>x \in L => P(V^{P}(x)=1)\ge \frac{2}{3} \ </tex>
+
==Определение==
 +
Классом '''IP'''[f(n)] ('''IP''' = interactive proof) называется множество языков, распознаваемых с помощью интерактивного протокола доказательства. При этом:
  
2) <tex>x \notin L => P(V^{Q}(x)=1)\le \frac{1}{3} \ \forall Q </tex>  
+
1) <tex>x \in L \Rightarrow \exists P : Pr(V^{P}(x)=1)\ge \frac{2}{3} \ </tex> , где <tex>Pr(V^{P}(x)=1)</tex> - вероятность того, что <tex>P</tex> убедит <tex>V</tex> допуститить <tex>x</tex>
 +
 
 +
2) <tex>\  x \notin L \Rightarrow \forall Q : Pr(V^{Q}(x)=1)\le \frac{1}{3} </tex>  
  
 
3) количество обращений к <tex>P \le f(n) </tex>
 
3) количество обращений к <tex>P \le f(n) </tex>
 +
 +
==Теорема==
 +
'''NP''' ⊂ '''IP'''[1], '''BPP''' ⊂ '''IP'''[0]
 +
 +
==Доказательство==
 +
Первое утверждение верно, так как определить, принадлежит ли слово языку, можно за один запрос. <tex>V</tex> посылает запрос к <tex>P</tex> и в ответ получает сертификат, если слово принадлежит языку. Если слово не принадлежит языку, то сертификата не существует, а значит <tex>P</tex> не может его послать. <tex>P</tex> хочет убедить <tex>V</tex> в том, что слово принадлежит языку, поэтому пришлет сертификат в случае его существования.
 +
 +
Второе утверждение очевидно, так как для проверки принадлежности слова к языку из [[Сложностный класс BPP|'''BPP''']] хватает вычислительной мощности <tex>V</tex>, и запросов к <tex>P</tex> делать не нужно.
 +
 +
==Замечание==
 +
На самом деле '''NP''' ⊂ '''dIP'''[1], где '''dIP'''[1] - аналог '''IP'''[1], за исключением того, что <tex>V</tex> из '''dIP'''[1] - детерминированная машина Тьюринга.
 +
 +
==Определение==
 +
'''IP''' = '''IP'''[poly] - класс языков, распознаваемых с помощью интерактивного протокола доказательства с полиномиальным числом запросов от <tex>V</tex> к <tex>P</tex>.

Текущая версия на 19:17, 4 сентября 2022

Определение

Интерактивный протокол доказательства - абстрактная машина, модулирующая вычисление как передачу сообщений между двумя сущностями: [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] хочет допустить слово тогда и только тогда, когда оно принадлежит языку.

Определение

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

1) [math]x \in L \Rightarrow \exists P : Pr(V^{P}(x)=1)\ge \frac{2}{3} \ [/math] , где [math]Pr(V^{P}(x)=1)[/math] - вероятность того, что [math]P[/math] убедит [math]V[/math] допуститить [math]x[/math]

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

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

Теорема

NPIP[1], BPPIP[0]

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

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

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

Замечание

На самом деле NPdIP[1], где dIP[1] - аналог IP[1], за исключением того, что [math]V[/math] из dIP[1] - детерминированная машина Тьюринга.

Определение

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