Implications of proving NP=RP on complexity theory 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?
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 &quot;yes&quot; 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$.