In August 2010, an enormous public relations opportunity fell into Computer Science’s lap, when Vinay Deolalikar’s attempt to separate P from NP resulted in unprecedented internet interest and media coverage.

I think it was a big success. (The outreach. Not the proof.) There are lots and lots of people who are interested in this stuff, and we should tell them more about it. Here are some reflections on my own tiny involvement.

Timeline

• On Sunday, 8 August, email from a former student pointed me to Greg Baker’s blog, which had announced Deolalikar’s manuscript the day before. Within two days, and perhaps largely due to Richard Lipton’s enthusiasm, hundreds of blog comments are written, and it is clear to me that this story could make it into regular news. Not because of the proof, but because of the collaborative model.
• Tuesday, 10 August, I write a crisp but comprehensive summary to the communications department at ITU Copenhagen, explaining the case, and my reasoning for why and how this could attract the attention of journalists. Luckily, they bite, and start pitching the story to Danish media.
• Wednesday, 11 August. The communication department gets back to me. Both venues I had in mind accepted: Danish public radio DR P1 Morgen and the weekly paper Weekendavisen. (I have appeared in both of these places previously, listen to the former and subscribe to the latter, so they are aimed at the demographic I am in.)

  Meanwhile, the story itself got even better: a wiki page at polymath has been created to discuss the proof. On the other hand, Deolalikar’s proof doesn’t fare too well because of problems with the structure of random k-Sat.

• Thursday, 12 August. I spend well over an hour in the morning talking to a journalist from DR P1 Morgen on the phone, to prepare for a radio interview for Saturday. This is how it works: she spends a lot of time and energy asking very good question and exploring various angles, actually really trying to understand what’s going on, scientifically. She then writes a brief intro and a list of possible questions and angles to the host of the radio show, who will conduct the broadcast interview.

  In the afternoon, I do basically the same hour-long phone interview with a journalist from Weekendavisen. WA’s deadline is Wednesday evening, so we aim for a longer piece in the paper’s science section next week.

  Meanwhile, Neil Immerman points to big problems with the finite model theory part of Deolalikar’s proof.

• Saturday, 13 August. I take an early train to Copenhagen, and enter the DR building. I’ve done this part once before, so I already feel like a jaded member of the chattering classes, going through the motions like a frequent airplane traveller through security. I announce my presence at the reception, receive a badge, and an assistant picks me up to lead me to a waiting area. The assistant gives me a brief chance to summarise what I’m going to talk about, probably this just to loosen my tongue. There’s coffee and morning papers. (Nothing about Deolalikar. I had hoped some major newspaper would falsely run the angle that “Outsider solves major math riddle, embarrassing reluctant ivory tower academics.” But no such luck.) After half an hour of waiting I’m ushered into the studio and get a bit more than the previously agreed 8 minutes to say the word algorithms as often as I can.
  • DR P1 Morgen summary (includes audio)

  I think it went well, though I still haven’t had the guts to hear it.

• Tuesday, 17 August. I should have had the Weekendavisen article for review by now, but WA has changed its overall design, including the software, so everything is running very late. (But they did change the body typeface to Garamond, making WA officially the best typeset paper on the planet. So all is forgiven, and my subscription renewal is guaranteed.)
• Wednesday, 18 August. I get the WA article, and I’m quite impressed. The angle is via Wiles and Perelman, then to collaborative software, outsourcing, and what I call the triumph of amateurism. Even some of my concerns about basic research funding are briefly touched upon, mathoverflow and polymath are mentioned. I know full well that I can’t change the angle anyway, but there are of course numerous problems with the details. Predictably, the article writes “mathematics” whenever it should write “computer science.” I spend some more time editing and send my changes back, fingers crossed.
• Thursday, 19 August. I get WA with my regular Swedish paper in the morning. The article is the front piece for the science section. (WA has no electronic edition I can link to. You have to buy it.)

Even though this all took a lot of time and energy, I’m pretty happy. The angle, i.e., collaborative math, turned out to be just right, and is the same that several other media have chosen. But remember this is all just a platform to say P, NP, algorithms, and complexity in public media as often as possible.

But it’s Wrong!

When doing something like this, know from the beginning that you have no bandwidth. You cannot explain anything. You have no time, and you have no visual aids. News media are neither very good at, nor even interested in, explanation of concepts. So don’t. And refrain from unnecessary precision. I wish I would learn.

The summary of the radio show includes the following (in my translation):

P versus NP is a scientific hypothesis that can be translated, very simplified, to the claim that there are problems that can be solved, and problems that can’t be solved.

Now, this is of course false. There are problems that cannot be solved, whole classes of them. Everything in UNDECIDABLE is undecidable no matter how much time you invest, and the problems in EXPTIME are infeasible in the sense that even though algorithms exist, they don’t run in polynomial time; we know P differs from EXPTIME by the time hierarchy theorem.

Would it have been worth correcting? No. The whole P versus NP problem loses a lot of its appeal once you start with “even though this claim is proved for some problems, there is a certain class of problems called NP for which this is not yet known.” Of course, the trick is instead to establish NP via verification versus computation, and I tried that both in the radio and the paper using Sudoku.

But the important thing is that none of this is the point. My mission is not to ventilate the correct definition of NP; anybody really interested can look it up on Wikipedia. I’ve had students who took whole classes from me who blissfully live in this misunderstanding. Those I try to correct, and sometimes successfully. But for the general public, I think this is unnecessary complication that only weakens the story.

I did get them to sneak “very simplified” in the summary, out of scientific integrity, and left it at that.

I can see that the New York Times currently has the same problem. A pretty good article from 16 August now has the following retraction:

Correction: August 21, 2010.
An article on Tuesday about a proposed solution of a classic mathematical formula called P versus NP described NP incorrectly and misidentified the location of the CERN physics research center. NP stands for the class of problems for which solutions can be verified relatively quickly, not the class of problems that are difficult to solve but easy to verify. And the CERN laboratory is near Geneva, not in Zurich.

Got it? I don’t.

The WA article contains a bigger mistake, and one I feel bad about. In my translation:

A 9×9 Sudoku is just big enough to entertain us during our morning coffee. But if we played Sudoku with letters instead of numbers, the number of combinations would be so huge, that all supercomputers on the planet would need until the end of the Universe to find a solution. “Unless, of course, there’s a really clever way to solve Sudokus that we just haven’t discovered yet,” adds Thore Husfeldt.

The usual Sudoku is a P-problem: it’s possible to write a recipe, an algorithm, to solve it. The big Sudoku is an NP-problem, one of the tasks mathematicians called Herculean, where you can use infinite time to check all combinations without ever finding the solution, but where you could immediately verify one if you had found it.

Vader voice: Noooo! This is the scientifically most ambitious part of the article, and contains crippling mistakes. All I can say is that it was worse when I got the first draft. Some of my edits made it (for example, it now no longer says that an 18×18 Sudoku contains twice as many cells as a 9×9 Sudoku.) Others, as you can see, didn’t. For completeness:

1. Sudoku is always NP-hard. The small ones are merely small enough that systematic exploration is still feasible. But for NP-hard problems, solution time presumably grows exponentially with problem size, so even the seemingly harmless increase to 25×25 alphabet Sodoku destroys any hope of solving it. (There’s more to say about the hardness of Sudoku. Maybe for another post.)
2. Even a 25×25 Sudoku still does not use infinite time. It’s a finite problem, after all. To a mathematician, 25×25 Sodoku is an easy problem, because the number of steps it takes is a small integer “close to zero”. But to a computer scientist, it’s important that this finite number of steps exceeds the computational power that remains in the universe for the rest of its lifetime. Yes, even if you install Ubuntu.
3. “Herculean” was a term suggested in Donald Knuth’s Herculean efforts to give NPC a better name.

Would another round of edits have made a difference? Probably. But because of the narrow schedule imposed by WA’s new layout engine, it was not to be. On the other hand, the new layout means I get to see my name in beautiful Garamond. I retain a weak spot for Aestheticism from my younger days, so I guess I will let the pleasures of form triumph over the constraints of content.

What I Should have Done

Next time, I will try with Impagliazzo’s five worlds, or rather two of them.

When trying to explain P versus NP, talk about Algorithmica versus Cryptomania instead. Morally, it’s the same problem, you need to worry about average-case complexity to see the difference. But it’s so much nicer to talk about. Algorithimica is a country in which you have Star Trek computers (or Skynet, depending no how much of an optimist you are), no mathematicians, etc. In Cryptomania you have crypto. We know that we live in one of these worlds (there are a few more), but we don’t know which. I think that’s a good way of putting it, because it conjures images. So that’s what I’ll try next time.

I just have to wait until the next proof attempt.