1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Определение==
'''Интреативный Интерактивный протокол доказательства''' - абстрактная машина, модулирующая вычисление как передачу сообщений между двумя частямисущностями: <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>'''IP'''[f(n)]</tex> ('''IP ''' = interactive proof) называется множество языков, распознаваемых с помощью интрактивного интерактивного протокола доказательства. При этом:
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 P\forall Q : Pr(V^{Q}(x)=1)\le \frac{1}{3} \ \forall Q </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>.
