Misplaced Pages

Toda's theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
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" and was given the 1998 Gödel Prize.

Statement

The theorem states that the entire polynomial hierarchy PH is contained in P; this implies a closely related statement, that PH is contained in 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 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.

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

Proof

The proof is broken into two parts.

  • First, it is established that
Σ P ⋅ B P ⋅ ⊕ P ⊆ B P ⋅ ⊕ P {\displaystyle \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 B P ⋅ ⊕ P {\displaystyle {\mathsf {BP}}\cdot \oplus {\mathsf {P}}} contains P {\displaystyle {\mathsf {P}}} and is closed under complement, it follows by induction that P H ⊆ B P ⋅ ⊕ P {\displaystyle {\mathsf {PH}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}} .
  • Second, it is established that
B P ⋅ ⊕ P ⊆ P ♯ P {\displaystyle {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}^{\sharp P}}

Together, the two parts imply

P H ⊆ B P ⋅ ⊕ P ⊆ P ⋅ ⊕ P ⊆ P ♯ P {\displaystyle {\mathsf {PH}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}^{\sharp P}}

References

  1. Toda, Seinosuke (October 1991). "PP is as Hard as the Polynomial-Time Hierarchy". SIAM Journal on Computing. 20 (5): 865–877. CiteSeerX 10.1.1.121.1246. doi:10.1137/0220053. ISSN 0097-5397.
  2. 1998 Gödel Prize. Seinosuke Toda
  3. Saugata Basu and Thierry Zell (2009); Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem, in Foundations of Computational Mathematics
  4. Saugata Basu (2011); A Complex Analogue of Toda's Theorem, in Foundations of Computational Mathematics
Categories: