Класс PCP

Определение

Классом PCP[r(n), q(n)] (PCP - Probabilistically Checkable Proof), где [math]n[/math] - длина входного слова, называется множество языков, распознаваемых машиной [math]V^{\pi}(x)[/math], обладающей следующими свойствами:

1) Время работы [math]V^{\pi}(x)[/math] ограничено сверху некоторым полиномом от длины [math]x[/math]

2) [math]\pi[/math] - некоторая строка, выступающая в качестве средства доказательства (аналогично P в интерактивном протоколе доказательства). Очевидно, ее длина не превосходит 2^poly(x), так как только к такому множеству позиций сможет обратиться [math]V[/math]

3) [math]V[/math] - вероятностная машина Тьюринга, обращающаяся к случайной ленте не более [math]q(n)[/math] раз

4) [math]V[/math] обращается к строке [math]\pi[/math] не более [math]r(n)[/math] раз

5) [math]x \in L \Rightarrow \exists \pi : Pr(V^{\pi}(x)=1)=1 \ [/math] , где [math]Pr(V^{\pi}(x)=1)[/math] - вероятность того, что [math]V[/math] допустит [math]x[/math]

6) [math]\ x \notin L \Rightarrow \forall \pi : Pr(V^{\pi}(x)=1)\le \frac{1}{2} [/math]