<p>A simple answer is that we're &quot;pretty sure&quot; that <span class="math-container">$\mathsf{P} \neq \mathsf{NP}$</span>, and we're &quot;pretty sure&quot; that <span class="math-container">$\mathsf{P} = \mathsf{RP}$</span>, so we're &quot;pretty sure&quot; that <span class="math-container">$\mathsf{NP} \neq \mathsf{RP}$</span>&quot;.</p>

CC BY-SA 4.0
2020-08-05T16:39:13.823Z
Yes, and more -- P != NP is conceptually interpreted as "the things we can efficently compute (P) do not include all NP problems". But conceptually RP and BPP also capture "things we can efficiently compute". So even if 'on a technicality' P != RP, we'd still say RP != NP has basically the same justifications as P != NP.
usul
CC BY-SA 4.0
2020-08-05T14:15:21.917Z
2020-08-05T14:15:21.917Z
Mahdi Cheraghchi
<p>The implication that PH collapses to BPP, and is therefore effectively tractable, is very distressing, but fortunately appears to be based on a confusion of randomized complexity classes. Zachos names a class R for which a supermajority of paths of a NP machine accept if the input is a member of the language, and all paths reject if not. The class RP in Sinclair's book, and hence for which their principal result might hold, is such that a bare majority of paths accept if the input is a member of the language, and all reject if not.</p>
<p>These two are not necessarily (or likely) to be the same class. Zachos' R is trivially contained in BPP, but as far as I can tell Sinclair's RP is not. So NP=RP (not R) would not imply NP contained in BPP.</p>

CC BY-SA 4.0
2020-08-05T18:42:45.427Z
Yes, these are the same. You get the same class of languages if the $1/2$ in the definition of RP is replaced by any other constant strictly between $0$ and $1$ (such as $3/4$, or whatever it is that "supermajority" means for you). See any textbook.
Emil Jeřábek
CC BY-SA 4.0
2020-08-05T18:48:25.310Z
That is incorrect. Any constant greater than ½, e.g. ⅔, can be replaced by another such constant, e.g. ¾, but ½ cannot. A bare majority could mean ½ + 2^(-n²), which cannot be amplified to an arbitrary threshold of probability in only polynomially many iterations.
Ben S
CC BY-SA 4.0
2020-08-05T18:49:22.660Z
This difference between bare majority and supermajority is the difference between PP and BPP.
Ben S
CC BY-SA 4.0
2020-08-05T18:54:28.343Z
You’re mistaken. What you say would be true for BPP, but for RP, an arbitrarily small positive constant is enough. Do see a textbook, as I already mentioned.
Emil Jeřábek
CC BY-SA 4.0
2020-08-05T19:10:04.590Z
Thank you, I get it now. Cunningham's Law works again!
Ben S
CC BY-SA 4.0
2020-08-05T19:19:33.260Z
No worries. ----
Emil Jeřábek
CC BY-SA 4.0
2020-08-12T17:17:13.747Z
@EmilJeřábek 1/2 in what? What if I just guess randomly? My probability of error will always be 1/2. Simple Yes or No is the output. There has to be a better definition of $RP$. Otherwise, NP=RP is trivial. I'm confused by wikipedia's definition. Because it all it says is 1/2 probability of guessing NO incorrectly. Which means not all yes's are correct. (and vice versa)
The T
CC BY-SA 4.0
2020-08-05T18:31:06.717Z
2020-08-05T18:31:06.717Z
Ben S
<p><em>Prelude: the below is just one consequence of <span class="math-container">$\mathsf{RP}=\mathsf{NP}$</span> and probably not the most important, e.g. compared to collapse of the polynomial hierarchy. There was a great and more comprehensive answer than this, but its author removed it for some reason. Hopefully the question can continue to get more answers.</em></p>
<p><span class="math-container">$\mathsf{P}/\mathsf{poly}$</span> is the set of decision problems solvable by polynomial-size circuits. We know <span class="math-container">$\mathsf{RP} \subseteq \mathsf{BPP}$</span> and, by Adleman's theorem, <span class="math-container">$\mathsf{BPP} \subseteq \mathsf{P}/\mathsf{poly}$</span>. So among the only mildly shocking implications of <span class="math-container">$\mathsf{RP}=\mathsf{NP}$</span> would be <span class="math-container">$\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$</span>.</p>
<p>Another way to put it is that instead of each &quot;yes&quot; instance of an <span class="math-container">$\mathsf{NP}$</span> problem having its own witness, there would exist for each <span class="math-container">$n$</span> a <em>single</em> witness string that can be used to verify, in polynomial time, membership of <em>any</em> instance of size <span class="math-container">$n$</span>.</p>

CC BY-SA 4.0
2020-08-05T10:12:52.920Z
Note that $NP \subseteq P/poly$ obviously implies that $NP \subseteq coNP/poly$, which is often assumed to not hold to prove kernelization lower bounds in parameterized complexity. $NP\subseteq coNP/poly$ is known to cause the polynomial hierarchy to collapse to the third level (which may be considered surprising).
user53923
CC BY-SA 4.0
2020-08-08T17:20:41.283Z
@VS I do not know, it would imply failure of ETH but that is all I found. Maybe it warrants asking a seperate question?
user53923
CC BY-SA 4.0
2020-08-05T04:51:16.947Z
2020-08-09T18:30:03.897Z
2020-08-09T18:30:03.897Z
usul
<p><strong>Edit:</strong> <em>As indicated below by Mahdi Cheraghchi and in the comments, the paper has been withdrawn. Thanks for the multiple excellent answers on the implications of this claim. I, and hopefully others, have benefited from them. It would probably be unfair to accept just one one answer in this case.</em></p>
<p>I apologise if this is off topic. In the paper just uploaded today (Edit: the paper is now withdrawn due to a flaw, see the comments below)</p>
<p><a href="https://arxiv.org/abs/2008.00601" rel="nofollow noreferrer">https://arxiv.org/abs/2008.00601</a></p>
<p>A. Farago claims to prove that NP=RP. From the abstract:</p>
<p><em>We (claim to) prove the extremely surprising fact that NP=RP. It is achieved by creating a Fully Polynomial-Time Randomized Approximation Scheme (FPRAS) for approximately counting the number of independent sets in bounded degree graphs, with any fixed degree bound, which is known to imply NP=RP. While our method is rooted in the well known Markov Chain Monte Carlo (MCMC) approach, we overcome the notorious problem of slow mixing by a new idea for generating a random sample from among the independent sets.</em></p>
<p>I am not an expert in the complexity hierarchies, why is this thought to be so surprising?</p>
<p>And what are the implications, if the claim is correct?</p>

CC BY-SA 4.0
2020-08-05T00:48:03.637Z
I am not asking about the correctness at all, but just the consequences of RP=NP. Yes, it will be interesting to see what happens.
kodlu
CC BY-SA 4.0
2020-08-05T04:42:22.690Z
"why is this thought to be so surprising?" For almost all the same reasons as P=NP, because RP is viewed as barely more powerful than P (if at all).
usul
CC BY-SA 4.0
2020-08-05T07:48:29.830Z
The paper does not pass the most basic smell test: it does not even *mention* relativization, let alone explain in credible detail how it overcomes this barrier.
Emil Jeřábek
CC BY-SA 4.0
2020-08-05T08:17:29.833Z
In the proof of Theorem 6 (page 16), the author writes, "If BPP-NP $\ne \emptyset$, then NP != co-NP must hold, since otherwise BPP would collapse into ZPP." This is under several assumptions, including NP = RP, NP = co-NP, and P != NP. How is the conclusion that, under these assumptions, BPP = ZPP reached?
user514014
CC BY-SA 4.0
2020-08-05T08:43:08.133Z
@VS. Relativization applies equally well to proofs of NP = RP as to proofs of $\mathrm{NP\ne RP}$.
Emil Jeřábek
CC BY-SA 4.0
2020-08-05T15:54:28.913Z
A user on reddit says that someone said that Peter Winkler has found a counterexample which has been acknowledged as valid by Andras Farago.
Giorgio Camerani
CC BY-SA 4.0
2020-08-05T16:03:59.347Z
Counterexample of Theorem 1 at the end of this thread: https://m.facebook.com/story.php?story_fbid=10221369856668363&id=1607304819.
Giorgio Camerani
CC BY-SA 4.0
2020-08-05T16:25:35.337Z
It's too bad that one needs to log in to a facebook account to view the discussion.
usul
CC BY-SA 4.0
2020-08-05T17:03:59.310Z
@usul user `Yuval Peres` said "I think Theorem 1 on p. 7 is false. The following counterexample uses the notation of the Theorem and is a modification of an example the author gives on p. 6. Take S={1,2,3} and H={1.2}. Let k=7 and let A be a sequence of T=n^k symbols that are IID 1 or 2, equally likely. Let B consist of T IID symbols that are 1 or 3, equally likely. Let X be either A or B with probability ½ each. Then H is ½- robust and \pi_H(2)=⅓, but \alpha(2) tends to ¼ as n tends to infinity.", and then "I wrote to the author as have several others. He told me he is withdrawing the paper."
Ramon Melo
CC BY-SA 4.0
2020-08-05T17:29:11.877Z
@user514014: The author answered my question on another thread. He wrote: "If NP=co-NP, then PH collapses to NP=co=NP. If also NP=RP, then NP=RP=co-RP. As BPP is in PH and contains RP, this means BPP=RP=co-RP. Since ZPP is the intersection of RP and co-RP we get BPP=ZPP."
user514014
CC BY-SA 4.0
2020-08-05T18:51:35.833Z
How does Yuval Peres get that $\alpha(2) \to 1/4$ as $n \to \infty$?
user514014
CC BY-SA 4.0
2020-08-05T19:59:39.057Z
@user514014 With probability 1/2, X=A, in which case all the elements are in H, and sampling them randomly gives 2 with probability 1/2. With probability 1/2, X=B, in which case you get 2 with probability 0. (I’m ignoring the corner case where B is disjoint from H, which happens with exponentially small probability. But this is why it is 1/4 only in limit.)
Emil Jeřábek
<cc.complexity-theory><np>
Implications of proving NP=RP on complexity theory
kodlu
# Implications of proving NP=RP on complexity theory

(Asked by: username_0 on 2020-08-04)

**Edit:** *As indicated below by Mahdi Cheraghchi and in the comments, the paper has been withdrawn. Thanks for the multiple excellent answers on the implications of this claim. I, and hopefully others, have benefited from them. It would probably be unfair to accept just one one answer in this case.*

I apologise if this is off topic. In the paper just uploaded today (Edit: the paper is now withdrawn due to a flaw, see the comments below)

<https://arxiv.org/abs/2008.00601>

A. Farago claims to prove that NP=RP. From the abstract:

*We (claim to) prove the extremely surprising fact that NP=RP. It is achieved by creating a Fully Polynomial-Time Randomized Approximation Scheme (FPRAS) for approximately counting the number of independent sets in bounded degree graphs, with any fixed degree bound, which is known to imply NP=RP. While our method is rooted in the well known Markov Chain Monte Carlo (MCMC) approach, we overcome the notorious problem of slow mixing by a new idea for generating a random sample from among the independent sets.*

I am not an expert in the complexity hierarchies, why is this thought to be so surprising?

And what are the implications, if the claim is correct?

**Tags:** cc.complexity-theory, np
> **Comments:**
> **username_0**: I am not asking about the correctness at all, but just the consequences of RP=NP. Yes, it will be interesting to see what happens.  
> **username_1**: "why is this thought to be so surprising?" For almost all the same reasons as P=NP, because RP is viewed as barely more powerful than P (if at all).  
> **username_2**: The paper does not pass the most basic smell test: it does not even *mention* relativization, let alone explain in credible detail how it overcomes this barrier.  
> **username_3**: In the proof of Theorem 6 (page 16), the author writes, "If BPP-NP $\ne \emptyset$, then NP != co-NP must hold, since otherwise BPP would collapse into ZPP." This is under several assumptions, including NP = RP, NP = co-NP, and P != NP. How is the conclusion that, under these assumptions, BPP = ZPP reached?  
> **username_2**: @VS. Relativization applies equally well to proofs of NP = RP as to proofs of $\mathrm{NP\ne RP}$.  
> **username_4**: A user on reddit says that someone said that Peter Winkler has found a counterexample which has been acknowledged as valid by Andras Farago.  
> **username_4**: Counterexample of Theorem 1 at the end of this thread: https://m.facebook.com/story.php?story_fbid=10221369856668363&id=1607304819.  
> **username_1**: It's too bad that one needs to log in to a facebook account to view the discussion.  
> **username_5**: @usul user `Yuval Peres` said "I think Theorem 1 on p. 7 is false. The following counterexample uses the notation of the Theorem and is a modification of an example the author gives on p. 6. Take S={1,2,3} and H={1.2}. Let k=7 and let A be a sequence of T=n^k symbols that are IID 1 or 2, equally likely. Let B consist of T IID symbols that are 1 or 3, equally likely. Let X be either A or B with probability ½ each. Then H is ½- robust and \pi_H(2)=⅓, but \alpha(2) tends to ¼ as n tends to infinity.", and then "I wrote to the author as have several others. He told me he is withdrawing the paper."  
> **username_3**: @user514014: The author answered my question on another thread. He wrote: "If NP=co-NP, then PH collapses to NP=co=NP. If also NP=RP, then NP=RP=co-RP. As BPP is in PH and contains RP, this means BPP=RP=co-RP. Since ZPP is the intersection of RP and co-RP we get BPP=ZPP."  
> **username_3**: How does Yuval Peres get that $\alpha(2) \to 1/4$ as $n \to \infty$?  
> **username_2**: @user514014 With probability 1/2, X=A, in which case all the elements are in H, and sampling them randomly gives 2 with probability 1/2. With probability 1/2, X=B, in which case you get 2 with probability 0. (I’m ignoring the corner case where B is disjoint from H, which happens with exponentially small probability. But this is why it is 1/4 only in limit.)  

---

## 3 answers

### Answer by username_1 on 2020-08-05. Score: 22 | Accepted answer

*Prelude: the below is just one consequence of $\mathsf{RP}=\mathsf{NP}$ and probably not the most important, e.g. compared to collapse of the polynomial hierarchy. There was a great and more comprehensive answer than this, but its author removed it for some reason. Hopefully the question can continue to get more answers.*

$\mathsf{P}/\mathsf{poly}$ is the set of decision problems solvable by polynomial-size circuits. We know $\mathsf{RP} \subseteq \mathsf{BPP}$ and, by Adleman's theorem, $\mathsf{BPP} \subseteq \mathsf{P}/\mathsf{poly}$. So among the only mildly shocking implications of $\mathsf{RP}=\mathsf{NP}$ would be $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$.

Another way to put it is that instead of each "yes" instance of an $\mathsf{NP}$ problem having its own witness, there would exist for each $n$ a *single* witness string that can be used to verify, in polynomial time, membership of *any* instance of size $n$.

> **Comments:**
> **username_9**: Note that $NP \subseteq P/poly$ obviously implies that $NP \subseteq coNP/poly$, which is often assumed to not hold to prove kernelization lower bounds in parameterized complexity. $NP\subseteq coNP/poly$ is known to cause the polynomial hierarchy to collapse to the third level (which may be considered surprising).  
> **username_9**: @VS I do not know, it would imply failure of ETH but that is all I found. Maybe it warrants asking a seperate question?  

---

### Answer by username_6 on 2020-08-05. Score: 6

A simple answer is that we're "pretty sure" that $\mathsf{P} \neq \mathsf{NP}$, and we're "pretty sure" that $\mathsf{P} = \mathsf{RP}$, so we're "pretty sure" that $\mathsf{NP} \neq \mathsf{RP}$".

> **Comments:**
> **username_1**: Yes, and more -- P != NP is conceptually interpreted as "the things we can efficently compute (P) do not include all NP problems". But conceptually RP and BPP also capture "things we can efficiently compute". So even if 'on a technicality' P != RP, we'd still say RP != NP has basically the same justifications as P != NP.  

---

### Answer by username_7 on 2020-08-05. Score: 0

The implication that PH collapses to BPP, and is therefore effectively tractable, is very distressing, but fortunately appears to be based on a confusion of randomized complexity classes. Zachos names a class R for which a supermajority of paths of a NP machine accept if the input is a member of the language, and all paths reject if not. The class RP in Sinclair's book, and hence for which their principal result might hold, is such that a bare majority of paths accept if the input is a member of the language, and all reject if not.

These two are not necessarily (or likely) to be the same class. Zachos' R is trivially contained in BPP, but as far as I can tell Sinclair's RP is not. So NP=RP (not R) would not imply NP contained in BPP.

> **Comments:**
> **username_2**: Yes, these are the same. You get the same class of languages if the $1/2$ in the definition of RP is replaced by any other constant strictly between $0$ and $1$ (such as $3/4$, or whatever it is that "supermajority" means for you). See any textbook.  
> **username_7**: That is incorrect. Any constant greater than ½, e.g. ⅔, can be replaced by another such constant, e.g. ¾, but ½ cannot. A bare majority could mean ½ + 2^(-n²), which cannot be amplified to an arbitrary threshold of probability in only polynomially many iterations.  
> **username_7**: This difference between bare majority and supermajority is the difference between PP and BPP.  
> **username_2**: You’re mistaken. What you say would be true for BPP, but for RP, an arbitrarily small positive constant is enough. Do see a textbook, as I already mentioned.  
> **username_7**: Thank you, I get it now. Cunningham's Law works again!  
> **username_2**: No worries. ----  
> **username_8**: @EmilJeřábek 1/2 in what? What if I just guess randomly? My probability of error will always be 1/2. Simple Yes or No is the output. There has to be a better definition of $RP$. Otherwise, NP=RP is trivial. I'm confused by wikipedia's definition. Because it all it says is 1/2 probability of guessing NO incorrectly. Which means not all yes's are correct. (and vice versa)  

---

