Toda's theorem
Toda's theorem 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. 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}. #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}
The proof is broken into two parts.
- First, it is established that
- The proof uses a variation of Valiant-Vazirani theorem. Because contains and is closed under complement, it follows by induction that .
- Second, it is established that
Together, the two parts imply
References
P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |
HPTS - Area Progetti - Edu-Soft - JavaEdu - N.Saperi - Ass.Scuola.. - TS BCTV - TS VideoRes - TSODP - TRTWE | ||