Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Source link: (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:

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

share|cite|improve this question
up vote 7 down vote accepted

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.

share|cite|improve this answer
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. – jcolebrand Jan 21 '11 at 1:16
  • 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.

share|cite|improve this answer
Yeah, and I think I have a bad title, but not sure exactly how to rephrase it. Open to suggestions. – jcolebrand Jan 20 '11 at 18:42
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). – Mitch Jan 20 '11 at 21:21
~ 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 – jcolebrand Jan 21 '11 at 1:18

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

share|cite|improve this answer
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... – jcolebrand Jan 20 '11 at 19:13

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.

share|cite|improve this answer

I like most people don't read P=NP? proofs. There seems to be something missing in the current approaches.

I have an approach that only lacks one step from resolving the issue. I only need to determine the complexity of determining membership in a fractal set. Decades more of work by me and I am sure I can resolve the final issues. Or not.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.