MA ⊆ AM

Inclusion · BM88

Statement

MA $\subseteq$ AM — BM88.

Sketch

Amplify the MA verifier’s soundness error below $2^{-\ell }/3$ by repetition on independent coins with the same witness, where $\ell$ bounds the witness length, then swap the order: Arthur sends his coins first and Merlin answers. A union bound over the $2^{\ell }$ possible Merlin messages bounds the soundness error of the swapped protocol by $1/3$; completeness holds because Merlin can ignore Arthur’s coins and send the MA witness.