# $\mathsf{PP=RP}$ consequences

We know $$\mathsf{PP=RP},\mathsf{coPP=coRP},\mathsf{PP=coPP=coRP=RP=ZPP=BPP\subseteq P/poly}$$ are equivalent and the polynomial hierarchy collapses to $2$nd level.

What are the other non-trivial collapses and consequences?

• PP is closed under complement so this probably isn't equivalent to PP=coPP. Nov 4, 2016 at 19:06
• My point is $p/poly$ contains everything I wrote. Nov 4, 2016 at 21:08
• I see, this is rather confusing, i would suggest editing to make this clearer, and avoid using the notation coPP (this is just confusing for the reader). Nov 4, 2016 at 21:17
• Also, since PP is closed under complement, you immediately get $PP=RP=ZPP$. Nov 4, 2016 at 21:22
• @Ariel oh right I will update. Nov 4, 2016 at 21:31

$\newcommand{\co}{\mathsf{co}\text{-}}$ $\newcommand{\class}[1]{\mathsf{#1}}$

If $\class{PP}=\class{RP}$ then you have a collapse to the first level, namely $\class{PH}=\class{NP}$.

Assume $\class{PP}=\class{RP}$, since $\class{PP}$ is closed under complement we have $\mathsf{RP}=\co{\class{RP}}=\class{ZPP}$, thus $\class{PP}=\class{ZPP}$.

Using Toda's theorem:

$\class{PH}\subseteq\class{P^{\class{PP}}}=\class{P}^{\class{ZPP}}=\class{ZPP}\subseteq{\class{NP}}$.

You actually get something stronger, if $\class{PP}=\class{RP}$, then the hierarchy collapses to $\class{ZPP}$.

In fact, you could show that the counting hierarchy collapses to $\class{ZPP}$, using simpler arguments than Toda's theorem, and acheive $\class{PH}\subseteq\class{CH}\subseteq\class{ZPP}$.

A tempting argument would be to say that since $\class{PP}=\class{ZPP}$, and $\class{ZPP}$ is low for itself, i.e. $\class{ZPP}^{\class{ZPP}}=\class{ZPP}$ then $\class{PP}^{\class{PP}}=\class{ZPP}^{\class{ZPP}}=\class{ZPP}$ and $\class{CH}$ collapses to $\class{ZPP}$. This is obviously false, since $\class{A}=\class{B}$ where $\class{A},\class{B}$ are sets of languages "decidable" by specific types of Turing machines (types $\class{A}$ and $\class{B}$), does not imply $\class{A}^{\mathcal{O}}=\class{B}^{\mathcal{O}}$ for any oracle $\mathcal{O}$. See this answer for further explanation.

What you actually need to show, in order to obtain $\class{CH}\subseteq{ZPP}$ (of course, under the original assumption of $\class{PP}=\class{RP})$, is that $\class{ZPP}$ is low for $\class{PP}$, i.e. $\class{PP}^{\class{ZPP}}=\class{PP}$. If this holds, then $\class{PP}^{\class{PP}}=\class{PP}^{\class{ZPP}}=\class{PP}=\class{ZPP}$, and thus $\class{CH}\subseteq\class{ZPP}$. Fortunately, this is not too difficult (and can even be strengthened to $\class{BPP}$ is low for $\class{PP}$).

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

$x\in L\Rightarrow \Pr\left[M_{\mathcal{O}} \text{ accepts x}\right]>\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 $<\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 $\class{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]>\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]>\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}<\frac{1}{2}-\frac{1}{2}2^{-n^c}$

Which proves $L\in \class{PP}$, since we can replace the constant $\frac{1}{2}$ with any function $f(x)\in \class{FP}$. See this question for a proof to why we can replace $\frac{1}{2}$ with any rational constant, and convince yourself that it generalizes immediately to any $f\in \class{FP}$.

• This argument is wrong. $\mathrm{PP=ZPP}$ does not in any way imply $\mathrm{PP}^X=\mathrm{ZPP}^X$ for every oracle $X$. In particular, the second level of CH collapses to $\mathrm{PP^{PP}=PP^{ZPP}}$, but not to $\mathrm{ZPP^{ZPP}}$. Thus, ZPP being low for itself is irrelevant, you’d need $\mathrm{PP^{ZPP}=PP}$ for the argument to go through. (However, the conclusion $\mathrm{PH=ZPP}$ is correct, as $\mathrm{PH\subseteq P^{PP}}$.) Nov 22, 2016 at 9:40
• And i thought i was passed this issue cs.stackexchange.com/questions/37626/…. Thank you for pointing it out, I will now roll back to the version that used Toda's theorem (as for now, I dont see how to avoid it). Nov 22, 2016 at 11:10
• I figured meanwhile that the conclusion is true as indeed $\mathrm{PP^{BPP}=PP}$ by a result of Köbler, Schöning, Toda, and Torán (there is a reference in the Complexity ZOO). Nov 22, 2016 at 11:13
• I added a proof for $\class{PP}^{\class{ZPP}}=\class{PP}$. The details made it a bit longer than i expected, so it might be worthwhile to just jump to the paper for the stronger statement (proofs are about the same length), but I think this is easier to understand. Nov 24, 2016 at 14:48
• Good work. Interestingly, already the weaker assumption $\mathrm{PP\subseteq P/poly}$ implies a similar collapse of the counting hierarchy: $\mathrm{CH=PP=MA=coMA}$. Nov 25, 2016 at 17:23