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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Определение)
Строка 1: Строка 1:
 
==Определение==
 
==Определение==
Интреативный протокол доказательства - абстрактная машина, модулирующая вычисление как передачу сообщений между двумя частями: <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> - 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> хочет допустить слово тогда, и только тогда, когда оно принадлежит языку.
 +
 
==Определение==
 
==Определение==
 
Классом <tex>IP[f(n)]</tex> (IP = interactive proof) называется множество языков, распознаваемых с помощью интрактивного протокола доказательства. Интрерактивный протокол доказательства - алгоритм, описывающий процесс передачи информации между двумя вычислительными машинами: <tex>P</tex> - prover и <tex>V</tex> - verifier.  При этом:
 
Классом <tex>IP[f(n)]</tex> (IP = interactive proof) называется множество языков, распознаваемых с помощью интрактивного протокола доказательства. Интрерактивный протокол доказательства - алгоритм, описывающий процесс передачи информации между двумя вычислительными машинами: <tex>P</tex> - prover и <tex>V</tex> - verifier.  При этом:

Версия 15:14, 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) называется множество языков, распознаваемых с помощью интрактивного протокола доказательства. Интрерактивный протокол доказательства - алгоритм, описывающий процесс передачи информации между двумя вычислительными машинами: [math]P[/math] - prover и [math]V[/math] - verifier. При этом:

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

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

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