7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ PP is closed under complement so this probably isn't equivalent to PP=coPP. $\endgroup$ – Ariel Nov 4 '16 at 19:06
  • $\begingroup$ My point is $p/poly$ contains everything I wrote. $\endgroup$ – T.... Nov 4 '16 at 21:08
  • 1
    $\begingroup$ 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). $\endgroup$ – Ariel Nov 4 '16 at 21:17
  • $\begingroup$ Also, since PP is closed under complement, you immediately get $PP=RP=ZPP$. $\endgroup$ – Ariel Nov 4 '16 at 21:22
  • 1
    $\begingroup$ @Ariel oh right I will update. $\endgroup$ – T.... Nov 4 '16 at 21:31
7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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}}$.) $\endgroup$ – Emil Jeřábek Nov 22 '16 at 9:40
  • $\begingroup$ 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). $\endgroup$ – Ariel Nov 22 '16 at 11:10
  • 1
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Nov 22 '16 at 11:13
  • 1
    $\begingroup$ 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. $\endgroup$ – Ariel Nov 24 '16 at 14:48
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Emil Jeřábek Nov 25 '16 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.