By now everyone knows about the new proposed proof that P $\ne$ NP by Vinay Deolalikar. Better minds than mine are on the case right now, and little snippets of questions are coming out in comments (especially on Dick Lipton's original post).
It's a little hard to keep track of all the discussions, so I thought I'd try a crowd-sourcing experiment. At this link is a google doc that contains some of the initial discussion topics being raised around the proof. It's crudely organized, with a section for each major set of issues, and paragraphs for each person's comment, with sourcing via URL.
It's editable, so here's the idea. As you see issues get raised and resolved, enter that into the doc. The following rules apply:
- No discussions: this should be comment/resolution only !
- No personal, or nontechnical commentary. This is purely for discussion of the mathematics involved, and nothing else
- Add references (urls, or whatever) whenever possible, and quote all context so as not to cause miscommunication.
Let's see if this works !
Colour me stupid, but how do you add the document (so you can use the latex editor mentioned in it)?
ReplyDeleteAlso, is there any "latest changes" mechanism?
Click on it as if to edit it. This will enter it into your docs folder on google docs. Now switch over to docs.latexlab.org. It will open a default document. Go to File -> Open, and ask to view ALL documents (not just starred ones), and then you will see this document in the drop down list.
ReplyDeleteIn google docs, you can look at revision history of a document.
Great idea. Hope that it works.
ReplyDeleteWith the new thread
ReplyDeletehttp://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p≠np
on Lipton's blog, I'd say that you already have the basic polymath structure: a research thread (Lipton's post), a discussion thread (this post), a wiki (the Google Doc), and (last, but definitely not least) a suitable group of participants and moderators. It will be interesting to see how this experiment evolves.
And now, the super simplified version, to keep the "bachelors in CS with vague remembrances of something involving capitals letters in an algorithms course" set interested:
ReplyDeletehttp://doespequalnp.com/
(and also http://ispequaltonp.com)
While the proof is being studied, I'm going to keep a one sentence update on there (the content reduction feels like an insult, but, well, that's the web these days), plus latest paper and discussion links.
I can't access the document. Error message: "There are currently too many people viewing this document. Please try again later."
ReplyDeleteMaybe there is a better venue than Google Docs.
Wow ! that's bizarre. I never thought that would happen. Let me see if I can do it elsewhere.
ReplyDeleteI wish it could be hosted somewhere other than google docs. For various reasons I don't wish to open a google account. Why not just use a blog post with a comment section? That's worked for the actual polymath projects.
ReplyDeletewait about 1 minute :)
ReplyDeleteSuch proof would have to cover all classes of approaches ... like continuous global optimization.
ReplyDeleteFor example in 3SAT problem we have to valuate variables to fulfill all alternatives of triples of these variables or their negations – look that
(x OR y) can be changed into optimizing
((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)
and analogously seven terms for alternative of three variables. Finding global minimum of sum of such polynomials for all terms, would solve our problem. (from www .scienceforums.net/topic/49246-four-dimensional-understanding-of-quantum-computers/ )
It's going out of standard combinatorial techniques to continuous world using gradient methods, local minims removing methods, evolutionary algorithms ... it's completely different realm: numerical analysis.
Such proof could work on concrete valuations, but here we work between them.
Does/can it cover also continuous approaches?