Toda's theorem

From Wikipedia, the free encyclopedia

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

$\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

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.