Tsuyoshi Ito respondeu a pergunta literalmente, mas queria comentar sobre a semântica do MA e do PCP e como elas diferem.
MA é a versão probabilística do NP, ou seja, o verificador também pode usar vários bits aleatórios.
No PCP, podemos nos referir à "aleatoriedade" do verificador, mas geralmente a aleatoriedade é logarítmica no tempo de execução do verificador, ou seja, o verificador poderia ter tentado todas as seqüências aleatórias possíveis por si só. Em outras palavras, essa "aleatoriedade" não comprará ao verificador qualquer poder computacional, diferentemente do caso do MA.
[Então, para que serve essa "aleatoriedade"? O objetivo do PCP é que, para verificação probabilística, basta um único teste - com um número constante de consultas à prova -]
Adendo (seguindo o comentário de Tsuyoshi): Nas caracterizações de NP por PCP, o tempo de execução do verificador pode ser policlarítmico e, da mesma forma, nas caracterizações de NEXP, o tempo de execução do verificador é polinomial. No entanto, a aleatoriedade nas construções de PCP é tipicamente usada apenas para escolher um teste (nas caracterizações de NP, dentre vários testes polinucleares, e nas caracterizações de NEXP, entre muitos exponencialmente) e não para ajudar no cálculo. Além disso, em MA, a prova é de tamanho polinomial, enquanto nas caracterizações de NEXP, a prova é de tamanho exponencial.