Something momentous happened this week. Of this I feel certain.
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.
I think you’re absolutely right, and it would be great to see this kind of high-speed peer review (and system of high standards for oneself and others) applied to arguments about things that have more real-world applications, like how to solve pressing economic problems. (I like purely theoretical problems like P=NP too, but if I had a choice, I’d rather see world hunger solved.)
Start with a question like “What would be the most effective way for the rich Western nations to end world hunger?” and then have proposed solutions or partial solutions posted in rigorous economic terms.
One big difference is that in mathematics, mistakes are unambiguously mistakes, while in discussions about world hunger, different people might disagree on what constitutes an error in reasoning or a mistaken assumption. I think the best way to address that problem would be: (a) narrow down disputes *as specifically as possible*, so that they center on the exact assumption or the exact reasoning step that people disagree on, and then (b) have peers vote on which side is correct.
My theory is that the more narrowly you drill down to the precise reasoning step that you think is erroneous, the more honest people will be with themselves and others about which side is correct. Even when an argument is sound, it’s easy for someone to shrug their shoulders and say they reject the entire argument, but harder for them to focus on a specific step in the reasoning and say that’s wha they disagree with — if indeed each step in the reasoning is correct.
Or, there may be other ways of doing it. But in general I’d like to see this kind of peer review and community debate applied to practical questions and not just theoretical ones.
I’ve been following it as well since Aaronson’s 200k bounty booster. Been interesting even though I understand 0 of the math.
Really looking forward to this last phase to see how Delalikar let’s go. So far he seems to be clinging to the proof and convinced he can be fix what he sees as small problems. One of the experts basically says his 100 pg proof actually proves pp!=ppp and that there is already a 1/2 pg proof of that in existence. Sounds like a huge problem.
Cannot imagine how much work and thought went into his “proof.” I assume years. Gotta be tough to admit you’re wrong.
I would be more impressed if the internet mind had done something creative, like actually prove whether or not P=NP. We’ve always been good at picking holes in other people’s proofs.
Neil: I would be more impressed if the internet mind had done something creative
Have a look at the discussion. In the course of pinpointing not just the holes in D’s proof, but the reasons those holes are unlikely to be fillable, a lot of new and potentially important mathematics got created on the fly (see the threads on polylog parameterizability, for example). (And a lot of previously known, but obscure mathematics, was clearly explained and made available for future exploitation.) I agree that if this were just a matter of shooting down a proof, it would be no big deal. But it is much much more than that.
Neil: or, say, find a new proof of the Density Hales Jewett Theorem? http://arxiv.org/abs/0910.3926
On Steve’s point – what is clear about this episode is that it just *isn’t* something that could happen on a regular basis, even as regular as, say, every six months. You can’t have Immerman and Lipton and Gowers and Tao and Impazagglio and… who knows how many others? drop their entire research programme and spend two days figuring out the details every time anyone claims to have a proof of an important theorem.
Scott Aaronson did the sensible thing and stayed well away – which is what most researchers do when most people from outside their specialty send them a proof of a famous unsolved problem. As Russell Impagliazzo said on day 1 – what is astonishing about this episode is not the concerted effort that was put into dissecting Deolalikar’s paper, but how exactly a from a non-expert which wasn’t even written as formal mathematics managed to create quite such a fuss.
I’m not necessarily saying that the fuss was a bad thing – getting Tao and Gowers interested in serious TCS questions can’t do the field any harm, and I’m sure some interesting maths will come out of it, but I am saying that we can’t make this sort of fuss over every purported proof of P!=NP, and we maybe need better heuristics to decide which ones are worth the effort.
Just for reference, I spelled Russell Impagliazzo’s name right the second time I used it, not the first.
Consequences will never be the same.
The same sort of live and public discussion is happening regarding monetary policy in response to Kocherlakota’s speech (which I am sure you are following). At the centre of the discussion are Williamson and Nick Rowe, with contributions of big names such as Andolfatto, Krugman, DeLong, M. Thoma, Rajiv Sethi and Jesus Fernandez-Villaverde.
This is indeed an exciting time, and I have been learning heaps!