tag:blogger.com,1999:blog-3722233.post2119159511121111565..comments2024-06-24T15:24:01.378-05:00Comments on Computational Complexity: The Humbling Power of P v NPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-89512332333116693982009-10-28T09:42:39.999-05:002009-10-28T09:42:39.999-05:00I'll not be giving up any time soon.
M. Micha...I'll not be giving up any time soon.<br /><br />M. Michael Musatov<br />http://meami.orgM-Wavehttps://www.blogger.com/profile/13408947017986840811noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51854986579011799422009-10-22T06:21:02.129-05:002009-10-22T06:21:02.129-05:00Gee, I thought The Humbling Power of P v NP was a ...Gee, I thought <i>The Humbling Power of P v NP</i> was a terrific topic ... it is a little bit surprising to rather few posts on it (so far).<br /><br />Perhaps a similarly appropriate but more provocative title might have been <i>The Flood-Tide and Ebb-Tide of P v NP</i>. <br /><br />Here "flood-tide" refers to Grothendieck's famous methaphor of a "rising sea" of abstraction in mathematics. The point being: Isn't it true that we now think about P vs NP at levels of abstraction that were unimagined with the problem was first formulated? And don't these new levels of abstraction (in Colin McLarty's words) help "clear away tangled multitudes of <br />individually trivial problems, put the hard problems in clear relief and makes their solution possible?"<br /><br />On the other hand, in practical engineering it generally happens that the individually trivial problems are what is chiefly of interest. Luckily for the engineering community, it is an empirical rule that every flood-tide of mathematical abstraction is followed by an ebb-tide of practical application; the wonderful book by Petkovsek, Wilf and Zeilberger titled <i>A=B</i> is a paradigmatic example of this.<br /><br />That is why (IMHO) students definitely *should* feel daunted by "the humbling power of P v NP" ... because heck ... just as Lance's post argues ... because modern complexity theory's rising sea of abstraction has focused and amplified this humbling power to an unprecedented degree. <br /><br />But these same students can await the ebb tide ... and contemplate with optimism and enterprise the immense scope of practical applications that the ebb tide is now revealing.<br /><br />Here too Grothendieck's letters reveal a penetrating understanding: <i>The question you raise "how can such a formulation lead to computations" doesn't bother me in the least! Throughout my whole life as a mathematician, the possibility of making explicit, elegant computations has always come out by itself, as a byproduct of a thorough conceptual understanding of what was going on. Thus I never bothered about whether what would come out would be suitable for this or that, but just tried to understand -- and it always turned out that understanding was all that mattered.</i><br /><br />A very important point is this: it isn't just the complexity theorists who are raising their level of abstraction to achieve (in Grothendieck's words) a "thorough conceptual understanding of what is going on." Pretty much every discipline in mathematics, science, and engineering is experiencing the same flood-tide of abstraction and ebb-tide of applications. <br /><br />This rich ebb-and-flood is good news for everyone IMHO ... because (as field ecology teaches us) ... it is inter-tidal zones that support the richest ecologists ... and historically this has been true in math, science, and engineering too.<br /><br />In summary, ebb-and-flood of modern mathematics makes it perfectly reasonable for students to feel *both* considerable humility *and* tremendous optimism.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39803292392228327352009-10-21T12:35:28.689-05:002009-10-21T12:35:28.689-05:00Great advice.
I spent many long nights as an und...Great advice. <br /><br />I spent many long nights as an undergrad with my latest proof of P = NP (or P != NP: depending on the height of snow in Ithaca, I was either optimistic or pessimistic). <br /><br />However, the resulting neglect of my classes led in part to an interesting grad school application adventure. So I would add one more piece of advice: Try to prove it, but only on weekends. (Or, become a grad student as early as possible, then try to prove it. My classmate Scott Aaronson had the right idea.)ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73931515219622666202009-10-21T12:16:00.624-05:002009-10-21T12:16:00.624-05:00Janos says: "As for the 'unreasonable eff...Janos says: <i>"As for the 'unreasonable effectiveness of polynomial time', at least part of the explanation is that researchers like to work in areas where one gets results..."</i><br /><br />---------------<br /><br />LOL ... that very phrase 'unreasonable effectiveness of polynomial time' often occurs to me at these synthetic biology seminars!<br /><br />But your remark is not quite correct about the second part. It is most commonly true in engineering (and in medicine too) that one *isn't* allowed to work in areas where results come easily.<br /><br />Instead one has to deal with whatever patients walk in the door ... or with an overheating planet with seven billion people on it ... with problems that are always messy and often seemingly intractable.<br /><br />And yet, polynomial resources very commonly are found to be "unreasonably effective" ... it seems that nature is "subtle but not malicious" in a complexity-theoretic sense that is remarkably general.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88909507105594658372009-10-21T11:27:31.217-05:002009-10-21T11:27:31.217-05:00Sorry. The problems you see tackled successfully a...Sorry. The problems you see tackled successfully are NOT NP-hard. They are tractable subcases of NP-hard problems.<br /><br />I agree that finding out what makes these subcases special IS a good research topic--or better set of research topics, as they are heavily problem-dependent.<br /><br />As for the "unreasonable effectiveness of polynomial time", at least part of the explanation is that researchers like to work in areas where one gets results, and that the quality of computational results only has to equal that of the experiments.CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55410733533580856362009-10-21T07:49:31.139-05:002009-10-21T07:49:31.139-05:00Here at the UW I've been attending David Baker...Here at the UW I've been attending David Baker's <i>Synthetic Biology Seminar</i>, an experience that suggests the following corollary to Nisan's suggestion: <br /><br /><i>"Early in their career every theorist should attend a seminar in which researchers tackle NP-hard problems with polynomial conmputational resources. Not to watch them fail, but to watch them succeed."</i><br /><br />The point is a Dick Lipton-esque one: there are genuinely mysterious aspects to the ubiquity of solvable problems in science and mathematics. <br /><br />This seems (to me) to be much the same thing that Noam Nisan is saying, approached from a different direction.John Sidleshttp://www.mrfm.orgnoreply@blogger.com