tag:blogger.com,1999:blog-3722233.post109655585525311467..comments2019-12-09T03:14:46.970-05:00Comments on Computational Complexity: The Specialization of Computer ScienceLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1118267561733013962005-06-08T17:52:00.000-04:002005-06-08T17:52:00.000-04:00P vs NP is an important problem. May be a very imp...P vs NP is an important problem. May be a very important problem but what's so deep about it?<BR/><BR/>A deep problem is one that explains a lot<BR/>of phenomenon in nature. So formulation of NP-Completeness was deep. But, how is P vs NP deep??<BR/><BR/>See, if you are getting obsessed by P vs NP its not because it is deep but its because you find it important! You are coming not from the perspective of interest but from your 'ego'. Andrew Wiles solved Fermat's last theorem - in what way<BR/>did it change the field of math? I suspect not. Go with what you find interesting rather then what you consider important...<BR/><BR/><BR/>SVAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1096898713053736492004-10-04T10:05:00.000-04:002004-10-04T10:05:00.000-04:00"As long as P vs. NP remains open, there will be o..."As long as P vs. NP remains open, there will be one thing that unites our field." Heh. Spoken like a true blue-blooded member of the STOC/FOCS dynasty.<br /><br />Most of the broader theoretical computer science community (SODA/SOCG/ALENEX/LICS/COLT/PODS/WAFR...) has about as much interest in P-vs-NP as any well-educated computer scientist or mathematician. We know what the question means, and we're happy to use it to boggle student minds ("You can win a million dollars by solving Tetris!"), but it has nothing whatsoever to do with our actual research interests. Just like Fermat's Last Theorem, the Poincare conjecture, and the four-color theorem, a huge body of intellectual effort has grown out of P-vs-NP, but by now the majority of that effort is completely unrelated to the original question.<br /><br />This is a GOOD thing.Jeff Ericksonhttps://www.blogger.com/profile/08256919779078679044noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1096578745555370332004-09-30T17:12:00.000-04:002004-09-30T17:12:00.000-04:00Always glad to start an argument. It's interestin...Always glad to start an argument. It's interesting to compare to recursion theory and set theory, which continued long after the main open problems were solved (by Friedberg and Muchnik in the 50's and Cohen in the 60's respectively). As far as I can tell, today these fields lack the kind of compelling narrative that complexity has, which might be why you see people moving from those fields to complexity but not vice versa. Even though most work in complexity has no direct bearing on P vs. NP, still the problem is there, like eerie background music that infuses every conference and workshop with a hint of the eternal.<br /><br />Speaking personally, if the P!=NP Proof From The Book fell to earth, and were already mined to show that NP is not in P/poly, NP is not in BQP, factoring is not in P, etc., I would probably switch fields to the foundations of quantum mechanics, which contains some of the only scientific mysteries deeper than P vs. NP. But as my grandmother might say, "oy gevult, that we should have such problems!"Scotthttps://www.blogger.com/profile/09428022255536654006noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1096572961802560762004-09-30T15:36:00.000-04:002004-09-30T15:36:00.000-04:00One might say that the unsolved Hilbert's problems...One might say that the unsolved Hilbert's problems unite all of math. But they don't, do they ? <br /><br />Although the fragmentation of theory CS is something to be regretted, it is also inevitable, and in a way is a success of individual areas at becoming richer and more advanced in their methods/problems/what have you.<br /><br />Isn't this a natural evolution of theory ? we should mourn the passing of an era, but not to the point where we try to reverse the trend. <br /><br />Maybe that's why math surveys have become so important. Like in Math, in theory we will have a (mostly) common language, the language of polytime and O() notation, and we will come to rely on surveys and other expository writing to bridge the gaps. It will become harder and harder though to have an impact across disciplines. <br /><br />What worried me more is the growing learning curve hump between quantum computing the rest of theory CS. that actually seems like a field with a very different base language...Sureshhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1096572553469668302004-09-30T15:29:00.000-04:002004-09-30T15:29:00.000-04:00This is an interesting idea, Scott. How much of TC...This is an interesting idea, Scott. How much of TCS is geared more-or-less directly toward resolving P/NP? Asked another way, if the P/NP Proof From The Book fell to earth tomorrow and was grokked by December, would a grad CS department still consider Theory applications for Autumn 2005? :) And in which subdisciplines?<br /><br />Personally, I can say that I am very interested in theory, but I don't think that P=NP or P!=NP would change that at all. Is this true in general, or is it that I do not understand the research correctly and a solution of P/NP would "sweep the rug out from under my feet"?<br /><br />Maybe I am crazy, but I find it very sad to consider that the field would fragment upon finding a formal answer to what _might be_ a pretty meaningless question.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1096568341481106622004-09-30T14:19:00.000-04:002004-09-30T14:19:00.000-04:00As long as P vs. NP remains open, there will be on...<I> As long as P vs. NP remains open, there will be one thing that unites our field.</I>Frustration?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1096566937650901862004-09-30T13:55:00.000-04:002004-09-30T13:55:00.000-04:00As long as P vs. NP remains open, there will be on...As long as P vs. NP remains open, there will be one thing that unites our field.Scotthttps://www.blogger.com/profile/09428022255536654006noreply@blogger.com