Theory of Computing
-------------------
Title : A Simple Proof of Toda's Theorem
Authors : Lance Fortnow
Volume : 5
Number : 7
Pages : 135-140
URL : http://www.theoryofcomputing.org/articles/v005a007
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 P^{parity-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.