Tuesday, August 10, 2010

A 'polymath' home for analysis of the Deolalikar proof

In collaboration with the Polymath project (and many thanks to Terry Tao for making this happen, and putting in lots of editing work in short order), there's now a new wiki to collect various threads of the discussion on the Deolalikar P != NP paper (which has been updated). With a lot of help from Terry, I've seeded the wiki with the initial discussion points that have come up. Please continue to edit this page as new ideas come up, or there's other discussion of the paper. 

This wiki replaces the Google doc that I had originally set up: it's a lot easier to edit, and Google was struggling under the weight of all the people trying to view the file.

The Lipton/Regan posts will continue to host the main research threads. If you are so inclined, you can use this post for "meta"-discussions as is customary in polymath land. Content will be transferred over to the wiki periodically, and more discussion threads can be forked if things start getting unwieldy (the first Lipton post is pushing 117 comments already).


  1. I started a section to collect typos and other trivial errors. This does not have much bearing on the essential correctness of the paper, of course, but given that we are directing a bunch of eyeballs at the paper, it seems like a "freebie" to add this to the page. (From past experience, it seems to me that wikis work best when there are a broad range of tasks that beckon for completion.)

  2. It seems the pace is set to slow down a bit, now that the paper has been at least temporarily withdrawn, and that enough unresolved issues with the paper exist to foster a healthy sense of skepticism. So it seems we won't need the full court press of a formal polymath project to completely deconstruct the paper after all, but I'm glad to see that the ability to have done so if necessary seemed to be in place.

  3. Terry, it's not clear to me whether the paper has been withdrawn. While the main link has been taken down, the documents are still accessible

  4. I've started a "Further reading" section. Many commenters over at Lipton's blog have asked for some places to start reading about some of the key concepts in complexity theory, finite model theory, etc. that have been involved. I think that while we still have a lot of experts crawling around the wiki, it would be good to start making a list. Unfortunately I myself am not an expert in the subject and can't really contribute, but perhaps others can.

  5. Should we start a section for news articles like this:

  6. There are many comments on the most recent Lipton post that deserve to be incorporated into the wiki. Especially the angle regarding error correcting codes, and the elaboration of the discussion involving XOR-SAT.

    Russell's objections should also be folded in


Disqus for The Geomblog