Изменения

# '''PCP'''[0, 0] = '''[[P|P]]''' (по определению '''P''' - нет случайности и обращений к <tex>\pi</tex>)# '''PCP'''[''log(n)'', 0] = [['''P]]''' (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)# '''PCP'''[0, ''log(n)''] = [['''P]]''' (логарифмическое число обращений к строке <tex>\pi</tex> также не помогают, так как можно аналогичным образом перебрать всевозможные результаты обращений за полиномиальное время)# '''PCP'''[''poly(n)'', 0] = '''[[Сложностные_классы_RP_и_coRP|co-RP]]''' (по определению '''coRPco-RP''')# '''PCP'''[0, ''poly(n)''] = '''[[NP|NP]]''' (по определению '''NP''' на языке сертификатов)# '''PCP'''[''log(n)'', ''O''(1)] = [['''NP]]''' ([[PCP-теорема]])