[Solved]: $\mathsf{PP=RP}$ consequences

Problem Detail: 

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?

Asked By : Turbo

Answered By : Ariel

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65557

3.2K people like this

 Download Related Notes/Documents