Toda's theorem is a result in

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

that was proven by

Seinosuke Toda is a computer scientist working at the Nihon University in Tokyo. Toda earned his Ph.D. from the Tokyo Institute of Technology in 1992, under the supervision of Kojiro Kobayashi. He was a recipient of the 1998 Gödel Prize for proving Toda's theor ...

in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998

Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...

Statement

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

Definitions

#P is the problem of exactly counting the number of solutions to a polynomially-verifiable question (that is, to a question in NP), 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 (polynomial time relative to a #P

oracle An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination. Description The word '' ...

). Thus Toda's theorem implies that for any problem in the polynomial hierarchy there is a deterministic

polynomial-time Turing reduction In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming ...

to a counting problem.1998 Gödel Prize. Seinosuke Toda
/ref> An analogous result in the complexity theory over the reals (in the sense of Blum–Shub–Smale real Turing machines) was proved by Saugata Basu and Thierry Zell in 2009Saugata Basu and Thierry Zell (2009)
''Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem''
in ''Foundations of Computational Mathematics'' and a complex analogue of Toda's theorem was proved by Saugata Basu in 2011.Saugata Basu (2011)
''A Complex Analogue of Toda's Theorem''
in ''Foundations of Computational Mathematics''

Proof

The proof is broken into two parts. * First, it is established that ::

\Sigma^P \cdot \mathsf \cdot \oplus \mathsf \subseteq \mathsf \cdot \oplus \mathsf

:The proof uses a variation of

Valiant–Vazirani theorem The Valiant–Vazirani theorem is a theorem in computational complexity theory stating that if there is a polynomial time algorithm for Unambiguous-SAT, then NP = RP. It was proven by Leslie Valiant and Vijay Vazirani in their paper ...

. Because

\mathsf \cdot \oplus \mathsf

contains

\mathsf

and is closed under complement, it follows by induction that

\mathsf \subseteq \mathsf \cdot \oplus \mathsf

. * Second, it is established that ::

\mathsf \cdot \oplus \mathsf \subseteq \mathsf^

Together, the two parts imply :

\mathsf \subseteq \mathsf \cdot \oplus \mathsf \subseteq \mathsf \cdot \oplus \mathsf \subseteq \mathsf^

References

{{reflist Structural complexity theory Theorems in computational complexity theory