Archive for August 11th, 2010

My pennyworth about Deolalikar

August 11, 2010

Given that I have expressed rather unambiguously an interest in the P/NP problem on this blog, I feel duty bound to make some kind of remark about Deolalikar’s recent attempt to prove the theorem. (If by some extraordinary chance you don’t know what I am talking about, then an excellent starting point is Dick Lipton’s blog, a link to which can be found in my blogroll.)

The problem is that I haven’t looked at Deolalikar’s paper in any detail, and already I can tell that I cannot possibly compete with the extremely knowledgeable comments that have been made by several TCS experts. So instead, let me say that, like everybody else, I greatly admire what Deolalikar has done, whether or not it turns out to be correct, and am happy to wait to see how things pan out.

Instead of commenting directly on his work, I thought I’d air some thoughts I had a few years ago. I was reminded of them by reading that an important feature of Deolalikar’s proof is that it uses uniformity in an essential way (though whether this is really the case has been disputed by some commenters). (more…)