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