ko_osaga's blog

NP=RP: P is almost NP?
By ko_osaga, history, 4 years ago, In English

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!

  • Vote: I like it
  • +769
  • Vote: I do not like it

Comments Comments (36)
| Write comment?
»
4 years ago, # |
  Vote: I like it +254 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +221 Vote: I do not like it

Don't get too excited, chance it is correct (even withiut opening it) is negligible

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    That's even worse than a randomly chosen scientific paper.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +89 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +62 Vote: I do not like it

    I mean, why is he so heavily downvoted? I feel like we need some air in this "constructive" heatpipe.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +44 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I don't even know what P,NP,RP is but this sounds cool.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +103 Vote: I do not like it

    How the fuck ddid you get 80 upvotes on such a nonsense comment

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +48 Vote: I do not like it

      Ratism probably

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -40 Vote: I do not like it

      How the fuck did you get 80 upvotes on such a nonsense comment

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it -32 Vote: I do not like it

        Hey, thanks for your question!

        There were several things about my comment that I believe led to a surge in upvotes:

        1. 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.

        2. 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,

        3. 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.

        4. 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!

        → Reply
»
4 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    To elaborate,

    I would bet on days taken to disprove rather than its true or false.

    It will be disproved within 5 days.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +64 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +187 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
  Vote: I like it +144 Vote: I do not like it

I have checked it guys ,completely correct! brilliant work ! keep it up !

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +81 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +90 Vote: I do not like it

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).

→ Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +58 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    What the fuck? And how did this bullshit get 50 upvotes? By the way, this paper was disproved.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      All you other slim shadys are just imitating, so won't the real slim shady, please stand up? please stand up? please stand up!

      → Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

it uses Hall's theorem, I feel like there should be a lot of experts in this field *cries in codejam*

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Editorial please !!!

→ Reply
»
4 years ago, # |
  Vote: I like it +288 Vote: I do not like it

look at Yuval's comments on Facebook here

src: Reddit

→ Reply
»
4 years ago, # |
  Vote: I like it -48 Vote: I do not like it

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”.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    But you're blue, that makes you an expert by definition!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +62 Vote: I do not like it

      I guess a little explanation is required.

      1. Before posting that comment, I scanned through full publication list of the author. It doesn't look like he specialises as a complexity theorist.

      2. 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.

      3. 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.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

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.

→ Reply