[Computational Complexity] My last post on the alleged P NE NP paper
- (This is likely my last post on the alleged P NE NP paper unless more real news on it occurs. The only real news I can see happening at this point is a retraction.)
I have not commented much on the alleged P ≠ NP since I was waiting for better informed or more opinionated people to comment first. Now that the dust has somewhat settled here is are some views of points of view and some pointers to points of interest.
- The best place to read about the technical details of the problems with the proof is Lipton's Blog Entries: here, here, here, here, here, and here. Also the Wikipedia entry here.
Some people are saying that
was nasty. Here is an excerpt from Scott's post:
What's obvious from even a superficial reading is that Deolalikar's manuscript is well-written, and that it discusses the history, background, and difficulties of the P vs. NP question in a competent way. More importantly (and in contrast to 98% of claimed P ≠ NP proofs), even if this attempt fails, it seems to introduce some thought-provoking new ideas, particularly a connection between statistical physics and the first-order logic characterization of NP. I'll leave it to the commenters to debate whether Deolalikar's paper exhibits one or more of the Ten Signs A Claimed Mathematical Breakthrough Is Wrong.Scott, that is downright nasty! Calling a paper well-written!! Accusing it of having thought-provoking new ideas!! Scott, you are just one Nasty dude!!
More seriously, Scotts offer of $200,000 if the proof is correct (more formally, if he wins the Mil prize) was considered nasty by some. Being skeptical and quantifing your skepticism is not nasty.
- Other posts worth looking at:
- Written pre-Deo, Lance now looks like Nostradamus: So you think you've settled P vs NP. (NOTE- personal triumph- I got the spelling of Nostradamus right on my first try!)
- A pre-Deo post of Scott's on 10 signs a claimed mathematical breakthrough is wrong. Deolalikar passed most of these.
- A post-Deo post of Scott's that was likely inspired by Deo: 8 signs your proof of P ≠ NP is wrong. One of Scott's signs cuts both ways- he says that the use of Descriptive Complexity Theory is one of the signs. He claims (correctly) ... subtle differences in encoding can lead to HUGE differences in computational complexity. Indeed, this was one of the problems with the Deo-Proof. However, I think Descriptive complexity theory is one of the few techniques that has not been proven cannot work. So I take its use as a good sign.
- Lance was on vacation when all of this happened so he posted on it when he got back. He was skeptical from the beginning and he says why. (See here.) People respond by saying that the paper inspired a lot of interesting discussion, and hence... I'm not sure- Lance shouldn't be skeptical? Lance shouldn't say he is skeptical? Lance should phrase his skepticism more politely? I'm not sure what the objection to his post really is.
- Is the proof correct? It looks like there are enough serious flaws that the answer for now is no. By now this is old news.
- I was originally skeptical (see here) since there has been no progress on P vs NP at all so its surprising that there is this much progress so fast. I do not know if this is valid reasoning. Has any serious hard math problem been solved all of a sudden after no progress on it? Has there truly been no progress? We might not know until we solve it in 3000 AD and look back and see which results from 1970-2010 ended up being relevant.
- Deolalikar should, by Thursday Aug 26, 2010 (the first day of Barriers II) either (1) retract the claim, or (2) post a version that fixes ALL of the flaws found and explains the fixes. If he does neither of these two things then he will cease to be a serious researcher.
- It would be impossible to have a version that fixes ALL of the flaws by Thursday Aug 26, 2010. Hence he needs to retract by then. (Some would say sooner. Much sooner. Like... now.)
- Was all of this good for the community? It got some talking and the people who read the proof learned some complexity. If this gets more people interested in the problem, that's got to be a good thing. If some interesting ideas come out of this, even indirectly (e.g., Terry Tao is inspired to read up on finite model theory and comes up with a result of interest) then it will of course be a good thing. However, if more of these proofs come out and the community spends too much time on them, that will be bad.
- Why did people take this paper so seriously?
- It was in LaTeX!
- It was long!
- It was by a respectable researcher. (More on that later.)
- It used familiar notation.
- It seemed to have some good ideas in. It may still. (More on that later.)
- It was on Slashdot and on Lipton's blog. But this begs the question: why was it on slashdot and why did Lipton take it seriously? Dick- I am not asking this rhetorically- if you read this please leave a comment about why you took it seriously. I am not asking this sarcastically or in any other nasty way. (I know YOU won't think so but other readers might.)
- Others took it seriously. Chicken and egg problem here.
- It had very few of the usual trademarks of papers written by cranks.
- It was a proof in the correct direction (a proof that P=NP would be taken less seriously, though the result, if true, would be more awesome!!!)
- In the age of the web, news travels fast (I know of 3 other serious people claiming to have shown P ≠ NP; however, that was pre-web so they were debunked before it got very far. I'm not quite sure which ones went public so I decline to mention their names.)
- How respectable a researcher is Deolalikar? I do not know any other work that he is done. He is not someone you've heard about as having done excellent work. The fact that some in the community took his work seriously is an excellent sign that our community is not elitist. They took it seriously based on its merits. (The fact that some did not take it seriously is irrelevant.)
- Are there interesting ideas in it? The answer from the latest comments by knowledgeable people on Lipton's blogs seems to be no. Oh well.
- In the midst of all of this came the DUMBEST comment on a post of mine EVER!! In a recent post I noted that a recent (2007) article on number theory still referred to factoring as being easy. I meant to imply that this was bad- they should at least acknowledge the issues involved even if they don't care. One of the comments was
Since when do mathematicians care about the notion of polynomial time?Note that this is the same week when Gowers and Tao, two Fields Medal winners, are carefully looking over an alleged proof that P ≠ NP. Other mathematicians were looking at it also. The notion that mathematicians do not care about polynomial time is just so 1990's.
- Other posts worth looking at:
Posted By GASARCH to Computational Complexity at 8/17/2010 08:47:00 AM