tag:blogger.com,1999:blog-3722233.post7808673758357566847..comments2020-07-09T17:10:19.118-04:00Comments on Computational Complexity: MoonshotsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-85920581270469620382015-12-07T06:55:01.366-05:002015-12-07T06:55:01.366-05:00The proof of Fermat's last theorem is a really...The proof of Fermat's last theorem is a really bad example here: of course the pop sci press stopped caring once a proof appeared, but (that bit of) the number theory community got right on with further work on the Langlands programme (FLT being a corollary of Wiles/Wiles-Taylor, which is a part of that). The effect was more or less the exact opposite of 'what now', rather more like 'hey, perhaps we could actually prove some of this big mass of conjectures, let's get to it'.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12164422279049435442015-12-03T15:31:04.482-05:002015-12-03T15:31:04.482-05:00I think there is a big difference between the P vs...I think there is a big difference between the P vs NP problem, and the moonshot. Reaching the moon was proposed as a prestige project, not really as a scientific challenge. We did know what we needed to do, there were several avenues to get there, and it was clear that what was needed was determination and money. <br />In contrast, the difficulty with attacking P vs NP is that we do not have good strategies to do so. It is not at all clear that throwing money at it would result in progress. <br />Hamming famously said that "The purpose of computing is insight, not numbers."<br />It seems hard to imagine that we could settle the question without making major advances in our understanding of what makes problems difficult, the nature of efficient computation, and other problems that are at the core of what Theoretical Computer Science is about. In particular, P vs NP is not THE problem--it is the poster child for a myriad of similar problems, all of them difficult, and, seemingly, all of them are difficult for the (not well understood at all) reasons.So, it is likely that a proof would give us new techniques, and new insights -- which would suggest further questions. <br />In particular, settling the P vs NP question might well leave many of the other interesting questions open. (Even if P=NP, what about P vs PSPACE? Arthur-Merlin games? etc. Of course, if P is not NP, we have a whole Complexity Zoo to explore....)<br />CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.com