Name
Abstract | ||
|---|---|---|
Toda in his celebrated paper showed that the polynomial-time hierarchy is contained in P#P. We give a short and simple proof of the first half of Toda's Theorem that the polynomial-time hierarchy is contained in BPP P. Our proof uses easy consequences of relativizable proofs of results that predate Toda. For completeness we also include a proof of the second half of Toda's Theorem. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.4086/toc.2009.v005a007 | Theory of Computing |
Keywords | Field | DocType |
relativization,toda's theorem,polynomial time | Analytic proof,Discrete mathematics,Combinatorics,Mathematical proof,Hierarchy,Completeness (statistics),Mathematics,Toda's theorem | Journal |
Volume | Issue | Citations |
5 | 1 | 3 |
PageRank | References | Authors |
0.38 | 5 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lance Fortnow | 1 | 2788 | 352.32 |