Volume 5 (2009) Article 7 pp. 135-140 [Note]
A Simple Proof of Toda's Theorem
Published: July 3, 2009
[PDF (150K)]    [PS (357K)]    [PS.GZ (118K)]
[Source ZIP]
Keywords: Toda's Theorem, relativization
ACM Classification: F.1.3
AMS Classification: 68Q15

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.