tag:blogger.com,1999:blog-3722233.post5413378436760495519..comments2022-12-09T08:43:59.127-06:00Comments on Computational Complexity: The Status of the P versus NP ProblemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-65614499215478299872010-08-05T05:50:31.874-05:002010-08-05T05:50:31.874-05:00Here is my proof of P=NP, a new theory, thanks htt...Here is my proof of P=NP, a new theory, thanks http://www.anhphamillusion.co.cc/website/pversusnp.htmlanhphamhttp://www.anhphamillusion.co.cc/website/pversusnp.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18877348833487541062009-09-01T08:03:21.549-05:002009-09-01T08:03:21.549-05:00Well, I intentionally sharpened the question by sa...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.<br /><br />About 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 ... <br /><br />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 ...Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37840277165297982972009-08-30T15:42:40.426-05:002009-08-30T15:42:40.426-05:00> nobody seriously thinks on this and because t...> nobody seriously thinks on this and because this is THE chicken of CS<br /><br />You'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 :-)<br /><br />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.<br /><br />> Well, some jung student could accidently solve this: P\neq NP. What will then change?<br /><br />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.<br /><br />> Real problems of CS are much more pragmatic<br /><br />I think you're confusing applied and theoretical CS. (And there are many interesting problems in theoretical CS apart from P vs. NP)<br /><br /><br />Yours sincerely,<br />A.B.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59996249508086837872009-08-28T16:04:03.711-05:002009-08-28T16:04:03.711-05:00Is somebody of us really interested in resolving t...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. <br /><br />Well, 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? <br /><br />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.Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35149476410367955272009-08-28T16:03:54.756-05:002009-08-28T16:03:54.756-05:00I think this article is excellent.
It's good ...I think this article is excellent.<br /><br />It'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.<br /><br />Not that it needed to be said, its publication proves as much, but given these Lance haters I thought I'd say it anyway.Lance fannoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89728277522177472832009-08-28T11:46:04.566-05:002009-08-28T11:46:04.566-05:00The line
If you said P is NP tonight
There would...The line<br /><br />If you said P is NP tonight<br /><br />There would still be papers left to write<br /><br />is from <br />THE LONGEST PATH,<br />one of the best theory songs ever written.<br />(Best one- I JUST DO THEORY)bil gnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12611616045489086312009-08-27T23:57:50.540-05:002009-08-27T23:57:50.540-05:00As a scientist, I think the state of the scientifi...As a scientist, I think the state of the scientific understanding where another question is answered is better than if it is not answered.<br /><br />Writing papers is a means for scientific understanding, it is not the other way round.<br /><br />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.<br /><br />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.Kamal Jainnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27020910547947121472009-08-27T20:28:43.005-05:002009-08-27T20:28:43.005-05:00Lance and Poita, has it not been said that if some...Lance and Poita, has it not been said that if someone said "P is NP" tonight, that there would still be papers left to write?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60564551485813665612009-08-27T19:16:31.937-05:002009-08-27T19:16:31.937-05:00The elaboration is in the next sentence.The elaboration is in the next sentence.Poita_https://www.blogger.com/profile/09778851161711133774noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12010819643787070752009-08-27T12:14:35.629-05:002009-08-27T12:14:35.629-05:00"Perhaps we will see a resolution of the P ve..."Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not."<br /><br />"...hope not." You hope not to see the resolution of P versus NP problem. This needs elaboration.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19182415094702484152009-08-27T09:14:03.299-05:002009-08-27T09:14:03.299-05:00This article appears to be open-access. I was abl...This article appears to be open-access. I was able to view it without first logging in to the ACM website.Anonymousnoreply@blogger.com