A little over a week ago, HP Research Scientist Vinay Delalikar claimed he could settle the central problem of theoretical computer science. That’s not the momentous part. The momentous part is what happened next.
Deolalikar claimed to prove that P does not equal NP. This means, very roughly, that in mathematics, easy solutions can be difficult to find. “Difficult to find” means, roughly, that there’s no method substantially faster than brute force trial-and-error.
Plenty of problems — like “What are the factors of 17158904089?” — have easy solutions that seem difficult to find, but maybe that’s an illusion. Maybe there’s are easy solution methods we just haven’t thought of yet. If Deolalikar is right and P does not equal NP, then the illusion is reality: Some of those problems really are difficult. Math is hard, Barbie.
So. Deolalikar presented (where “presented” means “posted on the web and pointed several experts to it via email”) a 102 page paper that purports to solve the central problem of theoretical computer science. Then came the firestorm. It all played out on the blogs.
Dozens of experts leapt into action, checking details, filling in logical gaps, teasing out the deep structure of the argument, devising examples to illuminate the ideas, and identifying fundamental obstructions to the proof strategy. New insights and arguments were absorbed, picked apart, reconstructed and re-absorbed, often within minutes after they first appeared. The great minds at work included some of the giants of complexity theory, but also some semi-outsiders like Terence Tao and Tim Gowers, who are not complexity theorists but who are both wicked smart (with Fields Medals to prove it).
The epicenter of activity was Dick Lipton’s blog where, at last count, there had been been 6 posts with a total of roughly 1000 commments. How to keep track of all the interlocking comment threads? Check the continuously updated wiki, which summarizes all the main ideas and provides dozens of relevant links!
I am not remotely an expert in complexity theory, but for the past week I have been largely glued to my screen reading these comments, understanding some of them, and learning a lot of mathematics as I struggle to understand the others. It’s been exhilarating.
Why is this momentous? In some ways, there’s nothing new about any of this. It’s not terribly uncommon for a serious looking paper to address a major outstanding problem, and it’s de rigeur for experts to comb through those papers, searching simultaneously for new paradigms, irreparable flaws, and salvageable insights. We call it peer review.
But what’s new is that this played out in public, and that it took a week instead of the usual months or years, and that the dozens of conversations taking place all over the world were melded into one giant conversation where every idea was available for everyone to hear—and for everyone to shoot down. Many very smart people said very smart things that turned out to be wrong, and in the world before the Internet, they might have gone on believing those things for weeks or months. The Net made it very difficult to believe wrong things for more than an hour.
It is a cliche to say that the Internet has changed everything, and in particular that it’s changed the way we do science. But what I saw this week seemed to me to be a whole new grand leap forward. The icing on the cake is the growing public record of everything that’s been said. Most of that record is a monument to the passion and dedication of a community obsessed with finding truth. In those thousand or so comments, I see almost nothing that smacks of self-aggrandizement, almost no instances where the proponent of an idea fails to back off instantly in the face of a better idea. Sometimes we in the academic community lose sight of how extraordinary are the high standards we routinely demand of ourselves and each other. Sometimes those outside of academics have no concept of how high those standards are. It’s inspiring to be reminded.
This week, there’s been no better inspiration—and no better education, and no better entertainment—than to read Dick Lipton’s blog.