None of us truly understands the P versus NP problem, we have only begun to peel the layers around this increasingly complex question. Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not. The P versus NP problem continues to inspire and boggle the mind and continued exploration of this problem will lead us to yet even new complexities in that truly mysterious process we call computation.Also a pre-publication version. Pure coincidence of having two CACM articles in a row, I don't have any more in the pipeline. If you missed it last month I told CS to grow up.
Thursday, August 27, 2009
The Status of the P versus NP Problem
Another month, another CACM article about another important and seemingly impossible to solve problem.
Subscribe to:
Post Comments (Atom)
This article appears to be open-access. I was able to view it without first logging in to the ACM website.
ReplyDelete"Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not."
ReplyDelete"...hope not." You hope not to see the resolution of P versus NP problem. This needs elaboration.
The elaboration is in the next sentence.
ReplyDeleteLance and Poita, has it not been said that if someone said "P is NP" tonight, that there would still be papers left to write?
ReplyDeleteAs a scientist, I think the state of the scientific understanding where another question is answered is better than if it is not answered.
ReplyDeleteWriting papers is a means for scientific understanding, it is not the other way round.
Lance, the complexities we discover in the absence of knowing whether P <> NP, are not as good as the complexities which will be discovered after knowing the answer. The resolution of P<>NP can either collapse the complexity world or confirm it, whatever be the case is, the new open question which will take the place of P<>NP will be more exciting, more enlightening, more challenging, and more revealing.
So I hope that you could change your "hope not" into hope. The resolution of P<>NP, requires that scientists like you not only be hopeful but confident in resolving the toughest scientific mystries. A sense of optimism, a ray of hope, and belief in yet unknown are part of the ingredients behind most scientific/mathematical discoveries.
The line
ReplyDeleteIf you said P is NP tonight
There would still be papers left to write
is from
THE LONGEST PATH,
one of the best theory songs ever written.
(Best one- I JUST DO THEORY)
I think this article is excellent.
ReplyDeleteIt's good for those new to the problem and for those like myself who have an abundance of interest in the problem, but a letters-after-their-name deficiency.
Not that it needed to be said, its publication proves as much, but given these Lance haters I thought I'd say it anyway.
Is somebody of us really interested in resolving the P vs. NP thing? Do we really want to kill our "chicken giving us golden eggs"? Eggs = advertising of CS for Math. and others. I also hope that nobody hopes P vs NP being solved in the nearest future. Just because nobody seriously thinks on this and because this is THE chicken of CS.
ReplyDeleteWell, some jung student could accidently solve this: P\neq NP. What will then change? Would we know more than now? Would we know that multiplication is harder than addition?
I think that P vs. NP is an overestimated problem. This is a "meta-problem". Real problems of CS are much more pragmatic. But we should let this problem "live" since it gives "golden eggs" (respect from other fields). If (when) this problem will die (=will be solved), the complexity theory will not--it will then go to its real tasks, from NP-completeness "madness" to proving real lower bounds for "simple" models.
> nobody seriously thinks on this and because this is THE chicken of CS
ReplyDeleteYou're wrong. Many brilliant computer scientists are working on P vs. NP and trying many interesting approaches. From Stephen Cook to Alexander Razborov and Lance Fortnow :-)
P vs. NP is not a buzzword for funding or advertisement. It is very important because it promotes different fields, e.g. circuit complexity or proof complexity.
> Well, some jung student could accidently solve this: P\neq NP. What will then change?
I think the solution of P vs. NP will require very useful and interesting mathematical tools. It's like Fermat's last theorem, but much more interesting since P \neq NP has many practical and theoretical consequences while the proof of FLT is interesting only because of its mathematical tools.
> Real problems of CS are much more pragmatic
I think you're confusing applied and theoretical CS. (And there are many interesting problems in theoretical CS apart from P vs. NP)
Yours sincerely,
A.B.
Well, I intentionally sharpened the question by saying "nobody is really working on P vs. NP". Of course, some of us are! Into the list of researchers you mentioned I would also include, say, Mike Sipser. Many years ago he told me about "diagonalization in finite domains", an idea which could apparently work. The whole thing stucks however on a hard combinatorics.
ReplyDeleteAbout the consequences of P\neq NP. What I claimed is that the separation *itself* will give us nothing, not the way towards this separation. But, so far, we can only speculate about what could happen along this unknown way ...
Shortly, replacing the goals of the whole TCS by just one "culminating" problem is not just the Fermat story. The last one was just one of many open problems in math ...
Here is my proof of P=NP, a new theory, thanks http://www.anhphamillusion.co.cc/website/pversusnp.html
ReplyDelete