\(\textbf{PP=RP}\) consequences

If \(\textbf{PP}=\textbf{RP}\) then you have a collapse to the first level, namely \(\textbf{PH}=\textbf{NP}\). Assume \(\textbf{PP}=\textbf{RP}\), since \(\textbf{PP}\) is closed under complement we have \(\textbf{RP}=co{\textbf{RP}}=\textbf{ZPP}\), thus \(\textbf{PP}=\textbf{ZPP}\).

Let \(L\) be a language in \(\textbf{PP}^{\textbf{ZPP}}\), then there exists a probabilistic polynomial time Turing machine with access to a \(\textbf{ZPP}\) oracle \(\mathcal{O}\), call it \(M_{\mathcal{O}}\), such that:

\(x\in L\Rightarrow \Pr \left[M_{\mathcal{O}} \text{ accepts x}\right]{\gt}\frac{1}{2}\), and

\(x\notin L\Rightarrow \Pr \left[M_{\mathcal{O}} \text{ accepts x}\right]\le \frac{1}{2}-\frac{1}{2^{n^c}}\).

Where \(n^c\) is the running time of \(M_{\mathcal{O}}\) (in the standard definition, the second inequality appears with \(\le \frac{1}{2}\), however it can be improved to \({\lt}\frac{1}{2}\) and thus to the above).

Suppose that the Turing machine which decides \(\mathcal{O}\) has expected runtime \(n^d\). Now, let us look at the machine \(M\), which replaces each oracle call of \(M_{\mathcal{O}}\) by a \(t\) steps simulation of the \(\textbf{ZPP}\) machine for \(\mathcal{O}\), and repeats this simulation \(k\) times. If we come upon an oracle call, for which this process did not result in an answer (none of the \(k\) \(t\)-steps simulations halted), then \(M\) rejects.

Let \(H\) denote the event that all of the simulations halted in the given time, then:

\(\Pr \left[\text{M accepts x}\right]=\Pr \left[\text{M accepts x} | H\right]\Pr [H]+\Pr \left[\text{M accepts x}\Big| \overline{H}\right]\Pr \left[\overline{H}\right]=\Pr \left[\text{M accepts x} | H\right]\Pr [H]=\Pr \left[M_{\mathcal{O}} \text{ accepts x}\right]\Pr [H]\).

Thus, we have:

\(x\in L\Rightarrow \Pr \left[\text{M accepts x}\right]{\gt}\frac{1}{2}\Pr [H]\), and

\(x\notin L\Rightarrow \Pr \left[\text{M accepts x}\right]\le \left(\frac{1}{2}-\frac{1}{2^{n^c}}\right)\Pr [H]\le \frac{1}{2}-\frac{1}{2^{n^c}}\).

By Markov’s inequality, a single simulation does not halt with probability \(\le \frac{n^d}{t}\), so \(k\) \(t\)-steps simulations do not output an answer with probability \(\le \left(\frac{n^{d}}{t}\right)^k\). By the union bound we have \(\Pr [H]\ge 1-n^c\left(\frac{n^{d}}{t}\right)^k\ge 1-\frac{1}{2^{n^c}}\), for \(t=2n^d\) and \(k=2n^c\). In this case \(M\) acheives the following separation:

\(x\in L\Rightarrow \Pr \left[\text{M accepts x}\right]{\gt}\frac{1}{2}\left(1-2^{-n^c}\right)\), and

\(x\notin L\Rightarrow \Pr \left[\text{M accepts x}\right]\le \frac{1}{2}-2^{-n^c}{\lt}\frac{1}{2}-\frac{1}{2}2^{-n^c}\)

Which proves \(L\in \textbf{PP}\), since we can replace the constant \(\frac{1}{2}\) with any function \(f(x)\in \textbf{FP}\).