Изменения

Можно считать, что строка <tex>\pi</tex> всегда такая, что пытается убедить <tex>V</tex> с максимальной вероятностью принять <tex>x</tex>. Если <tex>x \in L </tex>, то это происходить происходит с вероятностью 1, иначе с вероятностью не более <tex> \frac{1}{2} </tex>.

# '''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|coRPco-RP]]''' (по определению '''coRPco-RP''')# '''PCP'''[0, ''poly(n)''] = '''[[NP|NP]]''' (по определению '''NP''' на языке сертификатов)# '''PCP'''[''log(n)'', ''O''(1)] = [['''NP|NP]]''' ([[PCP-теорема]])