Изменения
→Определение
==Определение==
Классом <tex>IP[f(n)]</tex> (IP = interactive proof) называется множество языков, распознаваемых с помощью интрактивного протокола доказательства. Интрерактивный протокол доказательства - алгоритм, описывающий процесс передачи информации между двумя вычислительными машинами: <tex>P</tex> - prover и <tex>V</tex> - verifier. При этом:
1) <tex>x \in L => P(V^{P}(x)=1)\ge \frac{2}{3} \ </tex>
