Классом '''PCP[r(n), q(n)]''' ('''PCP''' - Probabilistically Checkable Proof), где <tex>n</tex> - длина входного слова, называется множество языков, распознаваемых машиной <tex>V^{\pi}(x)</tex>, обладающей следующими свойствами:
1) # Время работы <tex>V^{\pi}(x)</tex> ограничено сверху некоторым полиномом от длины <tex>x</tex>. 2) # <tex>\pi</tex> - некоторая строка, выступающая в качестве средства доказательства (аналогично P в [[Класс IP|интерактивном протоколе доказательства]]). Очевидно, ее длина не превосходит 2<sup>poly(x)</sup>, так как только к такому множеству позиций сможет обратиться <tex>V</tex>. 3) # <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]], обращающаяся к случайной ленте не более <tex>r(n)</tex> раз. 4) # <tex>V</tex> обращается к строке <tex>\pi</tex> не более <tex>q(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>)# '''PCP[log(n), 0] = [[P|P]]''' (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)# '''PCP[0, log(n)] = [[P|P]]''' (логарифмическое число обращений к строке <tex>\pi</tex> также не помогают, так как можно аналогичным образом перебрать всевозможные результаты обращений за полиномиальное время)# '''PCP[poly(n), 0] = [[Сложностные_классы_RP_и_coRP|coRP]]''' (по определению '''coRP''')# '''PCP[0, poly(n)] = [[NP|NP]]''' (по определению '''NP''' на языке сертификатов)# '''PCP[log(n), O(1)] = [[NP|NP]]''' ([[PCP-теорема]])
2) '''PCP[log(n), 0] = [[P|P]]''' (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)=Теорема==
3) '''PCP[0, log(n)] = [[P|PGNI]]''' ∈ '''PCP[poly(логарифмическое число обращений к строке <tex>\pi</tex> также не помогаютn), так как можно аналогичным образом перебрать всевозможные результаты обращений за полиномиальное времяO(1)]'''
4) '''PCP[poly(n), 0] = [[Сложностные_классы_RP_и_coRP|coRP]]''' (по определению '''coRP''')=Доказательство==
5) Алгоритм работы машины '''PCP[0V''' аналогичен алгоритму работы при доказательстве того, poly(n)] = что '''[[NP|NPGNI]]''' (по определению ∈ '''NPIP''' на языке сертификатов).
6) '''PCP[logВ строке <tex>\pi</tex> для каждого графа (nвведена некоторая нумерация графов)записано, O(1)] = [[NP|NP]]''' ([[PCP-теорема]])кому из данных графов <tex>G_1, G_2</tex> он изоморфен.
