25
правок
Изменения
→Свойства
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''')
