### ko_osaga's blog

By ko_osaga, history, 7 weeks ago,

Thanks to vintage_Vlad_Makeev for the information.

According to Wikipedia, RP is a class of decision problem which admits a randomized polynomial-time algorithm such that:

• If the correct answer is NO, it always returns NO
• If the correct answer is YES, then it returns YES with probability at least 1/2 (otherwise, it returns NO).

The Amazing Power of Randomness: NP=RP authored by Andras Farago claims that NP=RP. This means, there is a randomized polynomial time solution to NP problems, such as:

• 3-SAT
• Traveling Salesperson Problem
• Minimum Vertex Cover
• Graph Coloring
• Among others

What does it mean? Is the paper wrong? Should we start studying randomized algorithm instead of machine learning? Will all cryptographic system collapse?

• +769

 » 7 weeks ago, # |   +254 I think we should at least wait for confirmation (or more likely for found mistakes), because in my experience the major part of such claims turns out to be incorrect even if their author is as respectable as sir Michael Atiyah
•  » » 7 weeks ago, # ^ |   +105 (or try to confirm/disprove by ourselves, of course)
 » 7 weeks ago, # |   +221 Don't get too excited, chance it is correct (even withiut opening it) is negligible
•  » » 7 weeks ago, # ^ |   +21 That's even worse than a randomly chosen scientific paper.
 » 7 weeks ago, # | ← Rev. 3 →   +89 Obviously it means we need more randomized cp problems.To make it clear, I mean cp problems that use solutions with random algos, since this is a topic I feel has been hardly touched (yes I see why, hard to judge), and if this claim is true, or even if not, randomized algorithms is a large and important area of cs with many cool ideas.
•  » » 7 weeks ago, # ^ |   +62 I mean, why is he so heavily downvoted? I feel like we need some air in this "constructive" heatpipe.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   +44 I meant cp problems with solutions using random algos, I hope people didn't think I was bringing up that debate, but yes it is another way to increase variety in problems. I was thinking people just really hated problems with randomized solutions, but maybe they were down voting because they thought my comment was completely irrelevant, instead of just kinda irrelevant(lol), but idk maybe people do hate rand sol problems or thought it was still too irrelevant.
 » 7 weeks ago, # |   +11 I don't even know what P,NP,RP is but this sounds cool.
•  » » 6 weeks ago, # ^ |   +103 How the fuck ddid you get 80 upvotes on such a nonsense comment
•  » » » 6 weeks ago, # ^ |   +48 Ratism probably
•  » » » 6 weeks ago, # ^ |   -40 How the fuck did you get 80 upvotes on such a nonsense comment
•  » » » » » 6 weeks ago, # ^ |   -14 Binod
 » 7 weeks ago, # |   +42 RP is as good as P to be honest. One would rather use a RP solution than even a approximation/ machine learning algorithm.If it was true, corona would seem like a small insect.And we could all take vacation for a year, because the economic help would be much larger is NP==RPI mean they must be so desperate to even dare to post this shit on arxiv.
•  » » 7 weeks ago, # ^ |   +51 To elaborate,I would bet on days taken to disprove rather than its true or false.It will be disproved within 5 days.
•  » » 7 weeks ago, # ^ |   +64 Just glancing over the proof in the appendix, the runtime complexity of the proposed algorithm is $O(n^{k+9})$, where $k = 9$ for optimal results. So, even if the results were true, they are highly unpractical -- not even taking into consideration some large constant factor.
•  » » » 7 weeks ago, # ^ |   +187 Although I agree with your point, I don’t think that’s how we should approach things. I haven’t read the work yet but, if the paper would turn out to be correct, there would probably be a lot of improvement for the method in the near future, as well as alternative methods that would speed up the process. I think the hardest part is ‘breaking the gap’ between exponential and polynomial solutions.
•  » » » » 7 weeks ago, # ^ |   +2 True in general, but 'in the near future' is rather vague. I was specifically referring to the mentioning of the current pandemic in the comment by Clinking. It's not like all the problems in NP suddenly can be handwaved.
 » 7 weeks ago, # |   +144 I have checked it guys ,completely correct! brilliant work ! keep it up !
•  » » 6 weeks ago, # ^ |   +81 Thanks for checking! Apparently, some people haven't read it as thoroughly as you have. What do you think of this comment?Is it an invalid counterexample? Is Theorem 1 stated in an ambiguous way, so that you interpreted it in a different way that fills all the gaps? Again, thank you for your dedication to proofread this historical result.
 » 7 weeks ago, # |   +23 If the commonly believed conjecture P = BPP is true, then RP, co-RP, and P collapse (are all equal)This means that this is basically a Proof of P=NP, once the conjecture P = BPP (commonly believe to be true) is proved.
 » 7 weeks ago, # | ← Rev. 2 →   +90 Here is a link to a discussion on Reddit which helped me understand the perspective of the community a bit more (since I am hardly an expert on complexity theory). Summarizing the discussion from there, the proof approach seems to be similar to what would be expected to prove this, but most people believe there is some subtle mistake in the proof somewhere, since it would be extremely surprising if this was true.(Also, if anyone is interested, apparently the proof of Theorem 1 in the appendix seems to be crucial).
 » 7 weeks ago, # |   +7 I don't know about action in 'RP vs NP', but I know that every year there are dozens of papers claiming to prove NP==/!=P, which get debunked after a closer look at the proof. I would wait for an official statement by a conference or another institute.
 » 7 weeks ago, # |   +58 This was published within hours of the public being informed of Twice's upcoming October comeback. I bet tzuyu_chou was involved with this and she is very geniosity so I bet this paper is correct.
•  » » 6 weeks ago, # ^ |   -10 What the fuck? And how did this bullshit get 50 upvotes? By the way, this paper was disproved.
•  » » » 6 weeks ago, # ^ |   -13 All you other slim shadys are just imitating, so won't the real slim shady, please stand up? please stand up? please stand up!
 » 7 weeks ago, # |   -8 it uses Hall's theorem, I feel like there should be a lot of experts in this field *cries in codejam*
 » 7 weeks ago, # | ← Rev. 3 →   -8 I don't believe that this is completely true but if it is, it will be interesting to see that Knuth's opinion(afaik) is actually correct — there is a way to do it in polynomial time but not fast enough.
 » 7 weeks ago, # |   -29 Editorial please !!!
 » 6 weeks ago, # |   +288 look at Yuval's comments on Facebook heresrc: Reddit
•  » » 6 weeks ago, # ^ |   +78 :(
•  » » 6 weeks ago, # ^ |   +86 Who would have thought xd
 » 6 weeks ago, # |   -48 What does it mean? It means that we need to rise the bar. Namely, ignore those claims having an attitude of “here’s my huge convoluted proof, I myself am not sure about it, please check, for I am not an expert”.
•  » » 6 weeks ago, # ^ |   +1 But you're blue, that makes you an expert by definition!
•  » » » 6 weeks ago, # ^ |   +62 I guess a little explanation is required. Before posting that comment, I scanned through full publication list of the author. It doesn't look like he specialises as a complexity theorist. That "attitude" quotation is just a paraphrase of what the author has written in his paper. Okay, maybe I worded it unnecessarily harsh, but that's quite a characteristic of similar existing works: done by a CS researcher with apparently little relevant background, involves hard-to-disentangle argument, focuses on establishing truth of the statement rather than on developing tools that help to understand complexity landscape. The advice to ignore is not my own invention. It is a common stance among professional researchers (for example, https://www.scottaaronson.com/blog/?p=4916#comment-1851940 to appreciate how little they might care). If you don't know why, try to carefully read some other purported solutions to the P-vs-NP problem. Overall, I thought I was giving an honest advice. I understand that it probably was unwelcome. What I don't understand though is why you decided to respond to me like that.
 » 6 weeks ago, # |   0 essay unavailable???
•  » » 5 weeks ago, # ^ |   0 Theorem 1 was proven wrong by a counterexample, so the paper is withdrawn.
 » 5 weeks ago, # | ← Rev. 2 →   +16 Every time this blog reappears on the recent page, I check it to see if there’s any sequel to ‘The power of randomness’ bonanza.