Published: July 3, 2009
Abstract: [Plain Text Version]
Toda in his celebrated paper showed that the polynomial-time hierarchy is contained in $\P^\sharpP$. We give a short and simple proof of the first half of Toda's Theorem that the polynomial-time hierarchy is contained in $\BPP^\parityP$. 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.