MA ⊆ PP

Inclusion · Ver92

Statement

$\mathbf{MA}\subseteq \mathbf{PP}$: every language with a Merlin–Arthur proof system is decidable in unbounded-error probabilistic polynomial time — Ver92.

Sketch

Repeat the MA verifier on independent coins with the same witness, driving its error below $2^{-(\ell +2)}$, where $\ell$ is the witness length. A machine that samples a uniform witness and runs the amplified verifier accepts with probability at least $2^{-\ell }(1-2^{-(\ell +2)})\ge \frac{3}{4}\cdot 2^{-\ell }$ when $x\in L$ and at most $2^{-(\ell +2)}$ when $x\notin L$; shifting the separating threshold $2^{-(\ell +1)}$ to $1/2$ gives a $\mathbf{PP}$ machine — standard.

Notes

• No relativizing argument extends the containment to AM: there is an oracle relative to which $\mathbf{AM}⊈\mathbf{PP}$ — Ver92; see No relativizing reduction from AM to PP.