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