How valid is the proposed P=NP solution for the 3-SAT problem?

Question

Source link: http://romvf.wordpress.com/2011/01/19/open-letter/ (Referred from slashdot)

The fact of existence of the polynomial algorithm for 3-SAT problem leads to a conclusion that P=NP.

Is there validity to this argument that there is a P=NP solution? How long till this can be verified? Will this take years to verify or more likely weeks?

Final update:

http://cartesianproduct.wordpress.com/2011/02/27/no-proof-of-pnp-after-all-yet/

Vladimir Romanov has conceded that his published “proof” of P=NP is flawed and requires further work.

Answer 1

A cursory look at the paper reveals that the author is not a professional mathematician. The algorithm looks very simple, and the bibliography is extremely short. So according to Scott Aaronson's criteria (mentioned by svenkatr), the probability that this particular approach works is small.

This is aggravated by the statement in the website that the algorithm was already obtained in 2002, but the author waited for computer simulations - this makes no sense (either the proof works or it doesn't). Now it's true that in practice people can solve most SAT problems that they want to, probably much larger than the ones mentioned in the paper. But NP-hardness is about worst-case analysis.

The real question is whether this new proposed algorithm is faster in practice on real-world instances. The author has done no comparison, and so (since people have worked on optimizing the existing approaches), his method is probably worse than the competition.

Answer 2

• I won't try to address the 'Is there validity to this argument...?' except to say that it is number 65 out of 67 at the moment on The P-versus-NP page

• My guess is that, if the proof doesn't work, it will take a couple of weeks (if people who are able to judge care enough), but much longer the more substance it has. The last really serious proof attempt (Deolalikar, last August) took about a month before people ( a lot of serious computational complexity researchers) decided there were too many problems to bother continuing.

• But really, no matter what truth lies behind the claims, pretty much everybody will be expecting this to fail.

Answer 3

The problem with such a claim is that there are so many such claims made every year, not just for the P vs NP problem but other open problems as well. I am not an expert in this topic, so I won't comment on the content of the paper you have linked to.

In order to check claims of this sort, an expert will probably have to spend at least a few days (perhaps longer) to give a cursory reading of the paper. If it satisfies them at first glance (not a very easy task in itself), they will read through the arguments in the manuscript in detail and try find any possible flaws. Given the proliferation of such claims and how they have turned out, how will you convince an expert to invest the time and effort to give a basic reading of the manuscript first?

Check out this blog post by Scott Aaronson http://www.scottaaronson.com/blog/?p=122 . Does the manuscript you have linked to have an answer for most if not all the points that he is raising? Such a checklist can be helpful for people to decide whether a claim is worth checking in detail.

Answer 4

I haven't read the paper, but discussions I've seen of it indicate that it doesn't give an answer for all inputs, meaning that it doesn't really solve the problem.