{"id":4431,"date":"2010-08-17T06:35:27","date_gmt":"2010-08-17T13:35:27","guid":{"rendered":"http:\/\/palblog.fxpal.com\/?p=4431"},"modified":"2010-08-17T06:36:01","modified_gmt":"2010-08-17T13:36:01","slug":"complex-lessons","status":"publish","type":"post","link":"https:\/\/blog.fxpal.net\/?p=4431","title":{"rendered":"Proof?"},"content":{"rendered":"

For those of us with a passing (or greater) interest in algorithms, last week was particularly interesting: Vinay Deolalikar circulated a paper<\/a> that attempted to prove P\u2260NP. This is one of the great unsolved problems in Computer Science, and its solution has some important implications for real-world problems such as keeping your money in your bank account.<\/p>\n

I won’t attempt a summary of the proof, and will limit myself to social commentary.<\/p>\n

<\/p>\n

I find it interesting that a topic of central interest to theoretical computer scientists made it into the popular press within a week of its publication.\u00a0 As Richard Lipton pointed out<\/a> on the ACM Blog,<\/p>\n

The Internet has changed the way proofs can be examined, what once would have taken months or longer now can be done in days, if the occasion warrants. From Sunday to Friday there were many hectic exchanges of email, posts by the bloggers, comments from readers\u2014it was an unprecedented time.<\/p><\/blockquote>\n

From Lipton’s account, it is not clear whether Deolalikar had intended to release the paper publicly last week, but that is what happened. Because the work was obviously a serious attempt at solving the problem, it received considerable attention from\u00a0 complexity theorists; before significant flaws were discovered, it also reached the attention of the media.<\/p>\n

While this paper and the community’s response to it is a singular event, it may still serve as an example of the merits and perils of the publish-then-filter<\/a> model. On the one hand, Deolalikar appears to have failed in a very public way, whereas if he had submitted the paper to a journal only a handful of people would have read the manuscript. It would have taken them a lot of time (and a lot of secondary reviews) to decide whether the proof was valid. Given the magnitude of the claims, it seems likely that after a few months in the review pool, the flaws would have been found.<\/p>\n

On the other had, the public failure was a good thing for Deolalikar, for the complexity theory community, and for computer science as well. Deolalikar received much better and more thorough feedback on his approach much more quickly through this means than he might have otherwise, and there is no shame in this kind of failure. Even to have tried is a great accomplishment.<\/p>\n

The complexity theory community benefited because the attempt introduced new techniques for conducting such proofs, and this result may lead to many other discoveries and inventions. Had it remained locked in the confidential peer-review process, this methodology would have taken considerably less influential.<\/p>\n

Finally, computer science and applied mathematics disciplines benefit from the public airing of grand challenges because these debates may stir interest in these problems in kids looking for academic (and practical) challenges, something necessary for the long-term health of the discipline.<\/p>\n","protected":false},"excerpt":{"rendered":"

For those of us with a passing (or greater) interest in algorithms, last week was particularly interesting: Vinay Deolalikar circulated a paper that attempted to prove P\u2260NP. This is one of the great unsolved problems in Computer Science, and its solution has some important implications for real-world problems such as keeping your money in your […]<\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[218,18,58],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/posts\/4431"}],"collection":[{"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4431"}],"version-history":[{"count":5,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/posts\/4431\/revisions"}],"predecessor-version":[{"id":4433,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/posts\/4431\/revisions\/4433"}],"wp:attachment":[{"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4431"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4431"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4431"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}