If you can solve one NP-complete problem efficiently, you can do the same with any problem in NP. This is the crux of the Cook-Levin theorem [1], which lies at

If you can solve one NP-complete problem efficiently, you can do the same with any problem in NP. This is the crux of the Cook-Levin theorem [1], which lies at the heart of complexity theory. Now, while it's true that RP doesn't guarantee the correct answer 100% of the time, it does guarantee that the failure probability is bounded for every instance of the problem. This allows us to efficiently amplify the probability of having the correct answer to be arbitrarily close to 1. So in practice, RP and co-RP (and for that matter, BPP as well) are basically P for most practical purposes. [1] https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem