tag:blogger.com,1999:blog-3722233.post2232179220498361144..comments2024-03-04T02:59:26.350-06:00Comments on Computational Complexity: The Mystique of the Open ProblemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-61902556714390435002009-09-18T03:57:22.243-05:002009-09-18T03:57:22.243-05:00Rahul, I never heard of Gödel working on FLT. He ...Rahul, I never heard of Gödel working on FLT. He did do some work on the independence of the continuum hypothesis, that was found in his notes after his death, but experts examined what he had and while it was interesting, it didn't get anywhere near far enough to say that he anticipated Cohen's proof.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5794448874491289652009-09-13T10:13:55.881-05:002009-09-13T10:13:55.881-05:00In defense of Lance's choice of topic, the que...In defense of Lance's choice of topic, the question of P =?= NP is (IMHO) an ever-green question ... in the sense that the set of problems known to be in "P" is ever-expanding ... and the set of problems in "NP" is ever-expanding.<br /><br />Pretty much any thinking person sees that a train-wreck is coming soon ... a train-wreck not of mathematics, but of expectations! :)<br /><br />I was thinking of this when I attended a meeting of David Baker's group yesterday. The Baker group does compuzyme design ... you know ... designing large biological molecules from scratch?<br /><br />This biomolecular design problem is of course formally in NP ... the Baker group's toolset (both computational and experimental) obviously is in P ... so the task looks hopeless <i>prima facie</i> from the viewpoint of naive complexity theory ... and yet tremendous progress has been made in recent years.<br /><br />The rate of progress in synthetic biology is roughly the product of (1) the number of target applications, (2) the number of starting homologues, (3) the number of design variants of each homologue, (4) the <i>rate</i> at which the variants can be simulated (in Rosetta), (5) the <i>accuracy</i> with which the dynamics of the variants can be simulated, and (6) the rate at which the variants can be (physically) synthesized, and (7) the rate at which the structure of the variants can be validated by experimental observation, and (8) the rate at which the variants can be experimentally tested for biological activity.<br /><br />Now, it is evident that each of the preceding factors can be improved by 1-2 orders of magnitude ... "by developments of which we can already foresee <a href="http://www.pnas.org/content/106/8/2477.short" rel="nofollow">the character, the caliber, and the duration</a>" (in von Neumann's excellent phrase) ... and so we are looking at the arrival of a world (pretty soon!) in which the capabilities of synthetic biology are enhanced by an overall factor of 10^8--10^16.<br /><br />Of course, this is "only" a polynomial factor ... but it is a rather *big* polynomial factor, isn't it? ... it is (for example) the difference between creating one family-supporting job, and creating family-supporting jobs on a planetary scale.<br /><br />In this world, the set {"P"} and the set {"NP"} are going to adjoin one-another more closely than ever before ... and I agree 100% with Lance that we are guaranteed to learn a lot from this!<br /><br />This is what was meant in an earlier post when I asserted that three meetings this summer had "changed the world" ... these meetings being FOMMS, the Kavli/Cornell Conference on Molecular Imaging, and the ACS symposia on Conformational Biology (Rob Tycko's talk in particular).<br /><br />Nature magazine ran a series of articles in 2008 titled "Meetings that changed the world" ... the meetings that Nature selected were mainly meetings of program managers ... the meetings mentioned above were more like the Pocono Conference or Shelter Grove ... meetings attended mainly by scientists ... at which the world was changed mainly by the emergence of new horizons and a shared sense of new potentialities.<br /><br />I think Lance's post---and this whole Computational Complexity blog---contribute very substantially to this thrilling sense of "new horizons and new potentialities" ... for which I am very thankful.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15815606922201127402009-09-13T10:06:36.077-05:002009-09-13T10:06:36.077-05:00I'm wondering just exactly what problem will b...I'm wondering just exactly what problem will be solved if the P vs. NP problem will be solved? What I mean by that is what will become impossible or possible that we didn't already know was impossible or possible? It would seem that solving the P vs. NP question wouldn't tell us anything that we didn't already know outside of that one relationship. It that is the case, the question is of little importance. It it is an important puzzle to solve, then why is it important? By stating its importance, a clue might be given that could help solve the problem, if it can be solved.Unknownhttps://www.blogger.com/profile/02955547844743166800noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68152130419135441052009-09-13T09:45:03.533-05:002009-09-13T09:45:03.533-05:00but lance i am disappointed by the fact that you d...but lance i am disappointed by the fact that you didnt even reference your advisor`s work (as in his conference article) on PvsNP in both of your current papers.peternoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24549977868586466622009-09-13T09:40:20.297-05:002009-09-13T09:40:20.297-05:00haha last anon is funny.haha last anon is funny.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21593932990511763872009-09-12T20:25:08.566-05:002009-09-12T20:25:08.566-05:00Why is Lance harping on this P/NP thing? If you d...Why is Lance harping on this P/NP thing? If you don't have new things to blog, just don't blog that day.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19852117220133480352009-09-12T15:03:09.070-05:002009-09-12T15:03:09.070-05:00I wrote "Perhaps we will see a resolution of ...<i>I wrote "Perhaps we will see a resolution of the P versus NP problem in the near future <b>but I almost hope not </b>." </i><br /><br />...and everything was going great in that article until that sentence, whereupon I cringed.<br /><br />Given the relevance, as your article points out, of PvsNP research and its cousins to matters as serious as national security, it's just irresponsible to finish the article by saying sth like that.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42636806689141890362009-09-11T15:23:39.532-05:002009-09-11T15:23:39.532-05:00It is not necessary that everyone think alike---it...It is not necessary that everyone think alike---it is not even desirable!---but IMHO Lance's article nicely summarizes many cogent reasons for regarding P vs NP is <i>the</i> greatest open problem ... <br /><br />The nearest thing to a heterodox opinion that I came away with from Lance's article, was an equal admiration for upper-bound and lower-bound complexity theorems ... because we are similarly likely to make (what Lance's article calls) "inspiring and mind-boggling" discoveries in exploring both avenues.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2607268853373211602009-09-11T13:35:04.430-05:002009-09-11T13:35:04.430-05:00p vs np definitely does not have (2)p vs np definitely does not have (2)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3221104167779349172009-09-11T12:29:24.609-05:002009-09-11T12:29:24.609-05:00Thanks for writing the CACM article. As a recent a...Thanks for writing the CACM article. As a recent admit to the UW CSE department, the primer on P v NP was greatly appreciated.Evan Meagherhttps://www.blogger.com/profile/18202633935528318015noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85844616297968051472009-09-11T11:02:56.544-05:002009-09-11T11:02:56.544-05:00P vs NP can be stated to a layperson, though maybe...P vs NP can be stated to a layperson, though maybe not precisely. Yet all those mathematical clarifications take only away from the question (is polynomial time really the right notion and similar concerns.) People will understand the notion of efficiency without a mathematical underpinning.<br /><br />That said, the philosophical appeal of P vs NP cannot even be compared to Fermat's last theorem. Come one, no one cared about that question as such.<br /><br />If only some Russian mathematician in the 70's would have given a talk about P not being NP at the academy (doubtlessly under a title that would not make you guess subject of talk), and then vanished forever, we might have some mystery left, maybe even better than Fermat's rather cheesy attempt.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64225263764916007222009-09-11T11:00:36.250-05:002009-09-11T11:00:36.250-05:00As for the (3) aspect, isn't there a lost note...As for the (3) aspect, isn't there a lost notebook of Gödel containing a sketch of a proof, to which he cryptically refers in one of his letters?Rahulnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44994643034779438252009-09-11T10:40:01.611-05:002009-09-11T10:40:01.611-05:00Fermat's Last Theorem had
ALOT going for it be...Fermat's Last Theorem had<br />ALOT going for it before it was solved:<br />(1) Open,<br />(2) can be stated to the layperson,<br />(3) the myth that Fermat knew a proof -- the<br />``too big to fit in the margin'' notion sounds so<br />mysterious,<br />(4) Cash prize for it.<br /><br />P vs NP has (1) and (4).<br />(2) partially- depends on the layperson. (3) not at all.<br /><br />Even for ones OWN open problems it can be sad when they are solved since you were hoping to have it be a LONG STANDING OPEN PROBLEM!<br /><br />Fermats last theorem used to be what people would point to for an open problem in math.<br />What will they point to now? Goldbach's conjecture is pretty good<br />since you can tell it to a layperson and even do alot of examples.bil gnoreply@blogger.com