Toda's theorem
From HandWiki
Short description: The polynomial hierarchy is contained in probabilistic Turing machine in polynomial time
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"[1] 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
- 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). 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.[2]
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[3] and a complex analogue of Toda's theorem was proved by Saugata Basu in 2011.[4]
Proof
The proof is broken into two parts.
- First, it is established that
- [math]\displaystyle{ \Sigma^P \cdot \mathsf{BP} \cdot \oplus \mathsf{P} \subseteq \mathsf{BP} \cdot \oplus \mathsf{P} }[/math]
- The proof uses a variation of Valiant–Vazirani theorem. Because [math]\displaystyle{ \mathsf{BP} \cdot \oplus \mathsf{P} }[/math] contains [math]\displaystyle{ \mathsf{P} }[/math] and is closed under complement, it follows by induction that [math]\displaystyle{ \mathsf{PH} \subseteq \mathsf{BP} \cdot \oplus \mathsf{P} }[/math].
- Second, it is established that
- [math]\displaystyle{ \mathsf{BP} \cdot \oplus \mathsf{P} \subseteq \mathsf{P}^{\sharp P} }[/math]
Together, the two parts imply
- [math]\displaystyle{ \mathsf{PH} \subseteq \mathsf{BP} \cdot \oplus \mathsf{P} \subseteq \mathsf{P} \cdot \oplus \mathsf{P} \subseteq \mathsf{P}^{\sharp P} }[/math]
References
- ↑ Toda, Seinosuke (October 1991). "PP is as Hard as the Polynomial-Time Hierarchy". SIAM Journal on Computing 20 (5): 865–877. doi:10.1137/0220053. ISSN 0097-5397. http://epubs.siam.org/doi/10.1137/0220053.
- ↑ 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
![]() | Original source: https://en.wikipedia.org/wiki/Toda's theorem.
Read more |