8
$\begingroup$

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.

$\endgroup$

4 Answers 4

9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Excellent analysis. Thanks so much. I'm gonna give it a tad longer, but I have a feeling this is the answer worth accepting. I realize the peer reviews haven't been done, and a full assesment like that was never the intent of this question. $\endgroup$
    – jcolebrand
    Jan 21, 2011 at 1:16
8
$\begingroup$
  • 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.

$\endgroup$
3
  • $\begingroup$ Yeah, and I think I have a bad title, but not sure exactly how to rephrase it. Open to suggestions. $\endgroup$
    – jcolebrand
    Jan 20, 2011 at 18:42
  • $\begingroup$ It's a reasonable question as stated. The paper merits consideration. But to directly answer the question with only cursory examination of the paper would be intellectually dishonest (I really would like to gossip about it and have things to say, but I just don't think what I would say would be useful in math.stackexchange). $\endgroup$
    – Mitch
    Jan 20, 2011 at 21:21
  • $\begingroup$ ~ I admire that sentiment. I'm not asking anyone to make full academic dissertations on whether he's right or wrong, I'm just curious what the cursory philosophy on this is. I've actually got quite a few people who have seen this post that aren't necessarily math.SE users (they may be, but I doubt it) so it's nice to get a bead from people with more experience. Cheerio $\endgroup$
    – jcolebrand
    Jan 21, 2011 at 1:18
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks! I'll look into that link. Mostly tho, I should note somewhere, I'm the mathy person my geek friends turn to on these sorts of questions, so I was mostly just being curious. I'm honestly surprised this question hasn't been closed as NARQ or Subjective... $\endgroup$
    – jcolebrand
    Jan 20, 2011 at 19:13
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .