Toda's theorem

Remarks

The proof has two steps. First, $\mathrm{PH} \subseteq \mathrm{BPP}^{\oplus \mathrm{P}}$, where $\oplus \mathrm{P}$ is the class of languages decided by the parity of the number of accepting paths. This step uses the Valiant–Vazirani isolation lemma, which reduces satisfiability to unique satisfiability with random hash functions, applied level by level. Second, $\mathrm{BPP}^{\oplus \mathrm{P}} \subseteq \mathrm{P}^{\#\mathrm{P}}$. Here a polynomial transformation turns the parity of a count into a count modulo a large power of $2$. Then one call to a $\#\mathrm{P}$ oracle sums over all random strings at once.

The theorem can also be written $\mathrm{PH} \subseteq \mathrm{P}^{\mathrm{PP}}$, since $\mathrm{P}^{\mathrm{PP}} = \mathrm{P}^{\#\mathrm{P}}$, where PP is probabilistic polynomial time with unbounded error. By Valiant's theorem on the permanent, an oracle for the permanent of $0$-$1$ matrices decides every problem in PH in polynomial time.

Going deeper

For a student

Seinosuke Toda proved the theorem in 1991. It is surprising because a $\#\mathrm{P}$ oracle seems closely tied to a single NP machine, while PH involves many levels of NP oracles. Since $\mathrm{P}^{\#\mathrm{P}} \subseteq \mathrm{PSPACE}$, the theorem refines the inclusion $\mathrm{PH} \subseteq \mathrm{PSPACE}$. It also implies that if the permanent were easy, the whole polynomial hierarchy would collapse to P.