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" (1991) and was given the 1998 Gödel Prize.

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 which is correct at least half the time. The class P^#P consists of all the problems which 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). 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.^[1]

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 2009^[2] and a complex analogue of Toda's theorem was proved by Saugata Basu in 2011.^[3]

Proof

The proof is broken into two parts.

First, it is established that

\Sigma^P \cdot \mathsf{BP} \cdot \oplus \mathsf{P} \subseteq \mathsf{BP} \cdot \oplus \mathsf{P}

The proof uses a variation of Valiant–Vazirani theorem. Because

\mathsf{BP} \cdot \oplus \mathsf{P}

contains

\mathsf{P}

and is closed under complement, it follows by induction that

\mathsf{PH} \subseteq \mathsf{BP} \cdot \oplus \mathsf{P}

Second, it is established that

\mathsf{P} \cdot \oplus \mathsf{P} \subseteq \mathsf{P}^{\sharp P}

Together, the two parts imply

\mathsf{PH} \subseteq \mathsf{BP} \cdot \oplus \mathsf{P} \subseteq \mathsf{P} \cdot \oplus \mathsf{P} \subseteq \mathsf{P}^{\sharp P}

References

↑ 1998 Gödel Prize. Seinosuke Toda
↑ Saugata Basu and Thierry Zell (2009); Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem, in Foundations of Computational Mathematics
↑ Saugata Basu (2011); A Complex Analogue of Toda's Theorem, in Foundations of Computational Mathematics

This article is issued from Wikipedia - version of the 8/24/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.