Computers: Slightly Less Magic Than They Could've Been?

Our suspicions may have been confirmed: P may not have equaled NP all along.

The P=NP question has been the seminal problem in theoretical computer science since forever ago (for the computer value of forever: 40 years give or take). To simplify it past any resemblance of truth, P is basically the group of all 'easy' problems, and NP is the group of all 'easy to correct' problems. If I gave you a computer program and told you it could always win at chess, how would you go about confirming that's true? Not very easily. But if I told you there's a 3,000 mile car trip that visits every state capital in America, and tell you the roads to take, you'd just have to count up the miles to see if it's true. Proving a computer program does something is not in NP, but proving that there's a path of some length between cities is. The question, then, is if there's an easy way to confirm a solution is true, can you easily come up with the solution too? (If I give you a map, can you come up with the shortest path between all the state capitals?) Computer scientists have suspected 'no', but demonstrating this is true has been fraught with difficulty.

People try to prove this all the time, and they fail. Vinay Deolalikar apparently emailed a 100 page proof to a group of respected researchers, and the paper eventually ended up on the Internet. Then the Internet became abuzz, an article was written on slashdot, and tweets of 'Deolalikar' skyrocketed past any previous level he'd experienced. Daniel Lemire raised a good question: why? What about this proof has gotten such discussion, as opposed to countless other attempts at a proof? Which is a really interesting question in general.

News transmission requires two participants: someone to tell the news and someone to hear it. You're hearing, or rehearing, this news from me. All in all, I'll probably end up telling 15 or so individuals about this event. Each of you may pass the news on to someone new, or let this trail of the story of Deolalikar's proof attempt end.

Coincidently, just like in my last post linking auto-immune diseases, SEO and planted evidence there's a illness connection here. The study of news transmission began in the study of epidemics. Instead of giving you a disease, I'm giving you a fact. Sorry, antibiotics won't help this time. Maybe enough alcohol, consumed very quickly, will wipe the fact from your mind? On the plus side, P = NP would have been great news for robots, so Computer Science is arguably less likely to kill you now.

What was discovered in epidemics is that the crucial value for deciding if a sickness will turn into a pandemic is the average number of people a sick person passes the disease onto before dying or getting better. If they average, say, 0.9 people, then the disease will dwindle and vanish. But if the average is, say, 1.2 people, then it'll explode through the population, each day the legions of sick increasing. Same thing with zombies. Same things with news and memes.

The P=NP? proof is a particularly good example of this. The knowledge of this paper started out just in Deolalikar's head. He gave the paper to a few other researchers. If the proof was poorly done, it would have ended there. But it was exciting enough that the researchers wanted to share it with > 1 other person each. There was an initial outbreak of this knowledge, eventually reaching slashdot.

Slashdot, having a vast readership, is particularly apt at transmitting an idea. For an instant the average person told skyrocketed by its introduction. The analogy is that the virus has reached the water supply, or the zombies have entered New York City. There was a phase change in outreach.

Sometimes news sources provide stories that don't excite us, that don't have a viral spread > 1. These peter out of the public discourse. But the blog posts and tweets since the slashdot story demonstrate again that there's a viral nature to this story. And here I am telling you.

Viral spread isn't a constant value, as eventually the susceptible are all infected. And not everyone is susceptible, by genes or geographic isolation. Or in this case, interests. Not all the readers of this blog are computer science aficionados, so this is more likely to be the end of the line then the computer science-centric blogs I've read this story on. It still might have another major outbreak if it reaches a mainstream news source. Or alternatively, if other theoreticians can't find any problems with the proof the story will 'mutate', and grow even more viral. Million dollar prizes always make good stories.

Returning to Dan's question, what made the story viral? P=NP is about as pop-culture as unsolved mathematics can be. The proof is apparently plausible. Releasing the paper by email is novel and interesting. And "I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts" is a great way to announce one of the pinnacle proofs of our time.

One of the interesting things about viral spread is how small the critical value is. 0.95 people per iteration is a non-story, 1.05 can spread across the world. Thus it may be that the font comment was enough to push it across, and without it we'd have had to wait for more actual confirmation of the proof before hearing about it.

I find networks to be an endlessly interesting topic, and this is a great practical example of it. It also shows a news source acting as a facilitator of a story with wide popularity rather than pushing a story because of the source's reach. It'd be an interesting metric to see what news sources respond to and create viral spread, and which just push ideas that couldn't hold up in an organic global discussion.

As cool as a P=NP world would be, best of luck to Deolalikar, I hope you've earned your way into the pantheon of computer science greats.