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 Gödel 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. Classification
Statement FormCharacterization Theorem 1 Connections
Has Statement Form
In Branch
Source Toda's theorem, Wikipedia
Principal Result Of
Source Seinosuke Toda (Wikipedia)
Proved By
Source Toda's theorem, Wikipedia
In the Other Atlases
Credited To
Also in Computing Atlas: credited with this subject.
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, Seinosuke (October 1991)
Proved By: Seinosuke Toda, Lead sentence
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.
In Branch: Computational Complexity Theory, Lead sentence
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
In Group: Computability and Complexity Theory, Lead section
Toda's theorem is a result in computational complexity theory that was proven by Seinosuke Toda in his
View the SourceSeinosuke Toda (Wikipedia)
Principal Result Of: Seinosuke Toda, Lead, Toda's theorem prizeQuote, Principal Result Of: Seinosuke Toda, Lead, Toda's theorem prize
for proving Toda's theorem in computational complexity theory, which states that every problem in the polynomial hierarchy has a polynomial-time Turing reduction to a counting problem
Reader 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.