Класс IP

Определение

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

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]