Volume 5 (2009) Article 7 pp. 135-140 [Note]

A Simple Proof of Toda's Theorem

by Lance Fortnow

Received: January 21, 2009
Published: July 3, 2009

$ \newcommand{\sharpP}{\mathrm{\# P}} \newcommand{\parityP}{{\oplus\mathrm{P}}} \renewcommand{\P}{\mathrm{P}} \newcommand{\BPP}{\mathrm{BPP}} $

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.

DOI: 10.4086/toc.2009.v005a007

© 2009 Lance Fortnow
Licensed under a Creative Commons Attribution License (CC-BY)