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

A Simple Proof of Toda's Theorem

Received: January 21, 2009

Published: July 3, 2009

Published: July 3, 2009

**Keywords:**Toda's Theorem, relativization

**ACM Classification:**F.1.3

**AMS Classification:**68Q15

**Abstract:**
[Plain Text Version]

$
\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.