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?
Share your thoughts!
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
(or try to confirm/disprove by ourselves, of course)
Don't get too excited, chance it is correct (even withiut opening it) is negligible
That's even worse than a randomly chosen scientific paper.
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.
I mean, why is he so heavily downvoted? I feel like we need some air in this "constructive" heatpipe.
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.
I don't even know what P,NP,RP is but this sounds cool.
How the fuck ddid you get 80 upvotes on such a nonsense comment
Ratism probably
How the fuck did you get 80 upvotes on such a nonsense comment
Hey, thanks for your question!
There were several things about my comment that I believe led to a surge in upvotes:
I found a prime case of ratism in the CodeForces community. You were not saying anything constructive, yet you received 80 upvotes. One can only attribute this to your popularity in the CP community, which was a result of you having achieved an impressively high rating a young age. Many people who are relatively unpopular in the community (i.e me) yet add useful points to discussions often feel frustrated by such cases because it leads to an unfair gain in contribution for other people.
In such a technical post regarding complex mathematics, my comment provided an opportunity for comic relief. Amidst series discussions regarding the validity of the paper, I was acting frustrated over your gain in contribution via seemingly unimportant comments. Many programmers such as me who do not understand this paper got an opportunity to have a good laugh over the raw stupidity of your comment,
Ratism. If I am attributing your gain in contribution to ratism, I must be introspective and do the same for myself. I believe that some people may have just upvoted because they were interested in seeing two relatively high rated programmers have an argument on discuss.
Nobody likes you bitch sit down
I hope I've sufficiently answered your query, if you would like to learn more tips on how to effectively contribute to CodeForces blogs, do feel free to message me!
Binod
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==RP
I mean they must be so desperate to even dare to post this shit on arxiv.
To elaborate,
I would bet on days taken to disprove rather than its true or false.
It will be disproved within 5 days.
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.
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.
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.
I have checked it guys ,completely correct! brilliant work ! keep it up !
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.
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.
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).
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.
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.
What the fuck? And how did this bullshit get 50 upvotes? By the way, this paper was disproved.
All you other slim shadys are just imitating, so won't the real slim shady, please stand up? please stand up? please stand up!
it uses Hall's theorem, I feel like there should be a lot of experts in this field *cries in codejam*
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.
Editorial please !!!
look at Yuval's comments on Facebook here
src: Reddit
:(
Who would have thought xd
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”.
But you're blue, that makes you an expert by definition!
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.
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.