Цуёси Ито ответил на вопрос буквально, но я хотел прокомментировать семантику MA и PCP и то, как они различаются.
MA - это вероятностная версия NP, т. Е. Верификатор также использует много случайных битов.
В PCP мы можем ссылаться на «случайность» верификатора, но обычно случайность является логарифмической во время работы верификатора, то есть верификатор мог бы попробовать все возможные случайные строки сам по себе. Другими словами, эта «случайность» не дает верификатору никакой вычислительной мощности, в отличие от случая МА.
[Так для чего же эта «случайность»? Суть PCP в том, что для вероятностной проверки достаточно одного теста - с постоянным количеством запросов к доказательству - достаточно]
Приложение (после комментария Цуёси): В характеристиках PCP NP время выполнения верификатора можно сделать полулогарифмическим, и, аналогично, в характеристиках NEXP время выполнения верификатора является полиномиальным. Тем не менее, случайность в конструкциях PCP обычно используется только для выбора теста (в характеристиках NP, из поли-многих тестов и в характеристиках NEXP, из экспоненциально многих) и не помогает в вычислениях. Более того, в MA доказательство имеет полиномиальный размер, в то время как в характеристиках NEXP доказательство имеет экспоненциальный размер.