Изменения
Нет описания правки
2) <tex>\pi</tex> - некоторая строка, выступающая в качестве средства доказательства (аналогично P в [[Класс IP|интерактивном протоколе доказательства]]). Очевидно, ее длина не превосходит 2<sup>poly(x)</sup>, так как только к такому множеству позиций сможет обратиться <tex>V</tex>
3) <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]], обращающаяся к случайной ленте не более <tex>qr(n)</tex> раз
4) <tex>V</tex> обращается к строке <tex>\pi</tex> не более <tex>rq(n)</tex> раз
5) <tex>x \in L \Rightarrow \exists \pi : Pr(V^{\pi}(x)=1)=1 \ </tex> , где <tex>Pr(V^{\pi}(x)=1)</tex> - вероятность того, что <tex>V</tex> допустит <tex>x</tex>
6) <tex>\ x \notin L \Rightarrow \forall \pi : Pr(V^{\pi}(x)=1)\le \frac{1}{2} </tex>
==Свойства==
1) '''PCP[0, 0] = [[P|P]]''' (по определению '''P''' - нет случайности и обращений к <tex>\pi</tex>)
2) '''PCP[log(n), 0] = [[P|P]]''' (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)
3) '''PCP[0, log(n)] = [[P|P]]''' (логарифмическое число обращений к строке <tex>\pi</tex> также не помогают, так как можно аналогичным образом перебрать всевозможные результаты обращений)
4) '''PCP[poly(n), 0] = [[Сложностные_классы_RP_и_coRP|coRP]]''' (по определению '''coRP''')
5) '''PCP[0, poly(n)] = [[NP|NP]]''' (по определению '''NP''' на языке сертификатов)
6) '''PCP[log(n), O(1)] = [[NP|NP]]''' ([[PCP-теорема]])
