Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

NP=RP: P is almost NP?

Revision en1, by ko_osaga, 2020-08-04 13:47:00

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!

Tags p is, almost, np, wow

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ko_osaga 2020-08-04 13:47:00 991 Initial revision (published)