4 ms·
If this is true, it's about as close as you can get to P = NP for practical purposes. At a bare minimum, I'm pretty sure that would break all of modern cryptogr
by 3PS 6y ago
If this is true, it's about as close as you can get to P = NP for practical purposes. At a bare minimum, I'm pretty sure that would break all of modern cryptography outside of one-time pads. For that same reason, however, I think it's best to take this result with a grain of salt until it has passed peer review.
- centimeter 6y agoYep - the last time we saw a purported proof of P=NP, it was a very high quality effort from a respected researcher - but it had a small critical flaw. My money is on this being the same.
- tgv 6y agoBut doesn’t it only imply that an NP-complete problem can be solved with a certain probability in P time?
- 3PS 6y agoIf 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
- tgv 6y agoI knew the first part, but I had totally underestimated the importance of a lower bound on the probability, independent of the length of the input.