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