NP ⊆ PP

Inclusion · Gil77

Statement

$\mathbf{NP}\subseteq \mathbf{PP}$: every language in NP is in PP — Gil77.

Sketch

The $\mathbf{PP}$ machine flips one coin: on heads it accepts; on tails it samples a uniform candidate witness $w\in \{0,1{\}}^m$ and accepts iff the NP verifier accepts $w$. It accepts with probability $1/2+a/2^{m+1}$, with $a$ the number of accepting witnesses, which exceeds $1/2$ exactly on yes-instances.