UT Dallas Computer Science professor claims to have proven RP = NP | Hacker News Reader

UT Dallas Computer Science professor claims to have proven RP = NP

arxiv.org

88 points3PS13 comments

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.

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

But doesn’t it only imply that an NP-complete problem can be solved with a certain probability in P time?

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

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

Maybe the proof is wrong, but it looks quite likely to this will constitute an advance in our MCMC toolkit. In particular, I'd be curious if we can use his new MCMC method to create a probabilistical version of Schor's factorization algorithm. If NP=RP, this should be an easy consequence, but even if NP!=RP, it's possible (and some say even likely) that a classical version of Schor's algorithm exists.

Seems this paper is already withdrawn. Underneath the summary:

Comments: Paper is withdrawn because a counterexample was found to Theorem 1

Latest news I've heard (through informal channels) is that the paper is being withdrawn.

Are there demonstrations of how much faster or scalable an RP algorithm is for solving an NP-complete problem compared to the best known algorithms?

Vertex Cover is a well known problem that can be dropped to polynomial time with a random approximate algorithm.

I'm not entirely sure if approximate algorithms are included in RP.

To my understanding an approximate algorithm is one that technically solves a different problem. I don't think the approximate algorithms themselves form a complexity class because it's not sufficiently well defined how close an approximation is for an arbitrary problem. So it doesn't really make sense to ask if approximate algorithms are included in RP.

Although I suppose you could consider RP to be an approximate algorithm for a decision problem, although it doesn't guarantee it's close it just guarantees it's right at least x% of the time.

You are correct that approximate and random algorithms are quite different. An approximate algorithm is one that is guaranteed to give a solution that's approximate to within a in some sense, such as within a multiplicative factor of k, but in a deterministic time (generally polynomial). So, for instance, you could solve the TSP within 3/2 of the optimal length using Chrisofides algorithm[0].

In contrast, a randomized algorithm in RP is one which is guaranteed to be able to tell you whether there is no solution with 100% accuracy, but, if it says a solution exists, it is only correct to within some probability p. [1] A good example here is the Miller-Rabin primality test. [2,3]

---

[0]: https://en.wikipedia.org/wiki/Christofides_algorithm

[1]: https://en.wikipedia.org/wiki/RP_(complexity)

[2]: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...

[3]: Incidentally, although it's a little obscure, I did once manage to dig up the original paper that contained the elements of this algorithm. It was quite readable, IIRC. I may see if I can find it to post later.

A polynomial approximate algorithm is nice, but to actually solve the problem correctly/optimally don't you need a polynomial exact algorithm?

Reply on news.ycombinator.com