Toda's Theorem, proved by Seinosuke Toda in his 1991 paper PP is as Hard as the Polynomial-Time Hierarchy, is a result of computational complexity theory showing that the entire polynomial hierarchy is contained in P^PP, meaning every problem at any level of the hierarchy can be solved by a polynomial-time machine given access to an oracle for a counting problem. The result revealed an unexpectedly deep connection between counting complexity and the polynomial hierarchy and earned Toda the 1998 Godel Prize.
Facts
StatementThe entire polynomial hierarchy PH is contained in P^PP; this implies the closely related statement that PH is contained in P^#P. 1 Proof YearThe paper was published in October 1991. Sources
1. Toda's theorem, Wikipedia
Lead paragraph
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.
References, Toda 1991 entry
Toda, Seinosuke (October 1991)
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.