patternMinor
$\mathsf{PP=RP}$ consequences
Viewed 0 times
mathsfconsequencesstackoverflow
Problem
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?
What are the other non-trivial collapses and consequences?
Solution
$\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}\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}$.
$\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}\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}$.
Context
StackExchange Computer Science Q#65557, answer score: 7
Revisions (0)
No revisions yet.