PDMI TUM State University St. Petersburg
Steklov Institute St. Petersburg Technische Universität München State University St. Petersburg

Joint Advanced Student School (JASS)

Course 1: Proofs and Computers


St. Petersburg - Sunday, April 2 through Wednesday, April 12, 2006

Dmitry Shiryaev

Toda's Theorem, Part II

Abstract

Remember, Toda's Theorem states that $PH\subseteq P^{PP}$, where $PH$ is the polynomial hierarchy and $PP$ is the class of sets accepted by polynomial-time-bounded probabilistic Turing machines with two-sided unbounded error probability. Statement of the theorem can be proved by obtaining the chain of inclusions: $$PH\subseteq BPP^{\oplus P}\subseteq PP^{\oplus P}\subseteq P^{\# P}=P^{PP}$$ First inclusion was proved in the previous talk, here we will prove two rest inclusions and an equality.
So, proof will be divided in 3 steps: first, we remember some basic definitions, such as $BPP$, $PP$, $\oplus P$ and define some new class $\# P$. In that part we will also see, that first inclusion is evident, as $BPP\subseteq PP$. Second step is to show that $\# P$-oracle isn't more powerful than $PP$-oracle - and we get an equality $P^{\# P}=P^{PP}$. After all, the last and the main part of the paper is about the inclusion between $PP^{\oplus P}$ and $P^{\# P}$.



Dmitry Shiryaev Presentation:
Toda's Theorem II [PDF]
Paper:
Toda's Theorem II [PDF]