Tsuyoshi Ito respondió la pregunta literalmente, pero quería comentar sobre la semántica de MA y PCP y cómo difieren.
MA es la versión probabilística de NP, es decir, el verificador también puede usar múltiples bits aleatorios.
En PCP podemos referirnos a la "aleatoriedad" del verificador, pero generalmente la aleatoriedad es logarítmica en el tiempo de ejecución del verificador, es decir, el verificador podría haber intentado todas las cadenas aleatorias posibles por sí mismo. En otras palabras, esta "aleatoriedad" no le da al verificador ningún poder computacional, a diferencia del caso de MA.
[Entonces, ¿para qué sirve esta "aleatoriedad"? El punto de PCP es que para la verificación probabilística es suficiente una sola prueba, con un número constante de consultas a la prueba]
Anexo (siguiendo el comentario de Tsuyoshi): En las caracterizaciones de PCP de NP, el tiempo de ejecución del verificador puede hacerse polilogármico y, de manera similar, en las caracterizaciones de NEXP, el tiempo de ejecución del verificador es polinómico. No obstante, la aleatoriedad en las construcciones de PCP generalmente se usa solo para elegir una prueba (en caracterizaciones de NP, de múltiples pruebas, y en caracterizaciones de NEXP, de exponencialmente muchas) y no para ayudar con el cálculo. Además, en MA, la prueba es de tamaño polinómico, mientras que en las caracterizaciones de NEXP, la prueba es de tamaño exponencial.