43
правки
Изменения
Новая страница: «===Определение=== Классом <tex>IP[f(n)]</tex> (IP = interactive proof) называется множество языков, расопознава…»
===Определение===
Классом <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> (<tex>P</tex> не видит вероятностную ленту <tex>V</tex>). <tex>V</tex> хочет допустить слово тогда, и только тогда, когда оно принадлежит языку. При этом:
1) <tex>x \in L => P(V^{P}(x)=1)\ge \frac{2}{3} \ </tex>
2) <tex>x \notin L => P(V^{Q}(x)=1)\le \frac{1}{3} \ \forall Q </tex>
3) количество обращений к <tex>P \le f(n) </tex>
Классом <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> (<tex>P</tex> не видит вероятностную ленту <tex>V</tex>). <tex>V</tex> хочет допустить слово тогда, и только тогда, когда оно принадлежит языку. При этом:
1) <tex>x \in L => P(V^{P}(x)=1)\ge \frac{2}{3} \ </tex>
2) <tex>x \notin L => P(V^{Q}(x)=1)\le \frac{1}{3} \ \forall Q </tex>
3) количество обращений к <tex>P \le f(n) </tex>
