Toda's theorem


Toda's theorem is a result in computational complexity theory that was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize.

Statement

The theorem states that the entire polynomial hierarchy PH is contained in PPP; this implies a closely related statement, that PH is contained in P#P.

Definitions

is the problem of exactly counting the number of solutions to a polynomially-verifiable question, while loosely speaking, PP is the problem of giving an answer that is correct more than half the time. The class P#P consists of all the problems that can be solved in polynomial time if you have access to instantaneous answers to any counting problem in #P. Thus Toda's theorem implies that for any problem in the polynomial hierarchy there is a deterministic polynomial-time Turing reduction to a counting problem.
An analogous result in the complexity theory over the reals was proved by Saugata Basu and Thierry Zell in 2009 and a complex analogue of Toda's theorem was proved by Saugata Basu in 2011.

Proof

The proof is broken into two parts.
Together, the two parts imply