P versus NP

A researcher from HP Labs named Vinay Deolalikar announced a new proof that complexity classes P and NP are different. The paper made it to the Slashdot front-page (more on this below).

What constitutes a “proof”?

This is far from being the first claimed proof. There are about as many proofs that P is the same as NP than proofs of the opposite. With, for good measure, a few papers claiming that this is really undecidable… This just shows that the problem is not solved just because of one more paper. Indeed, the new “proof” takes more than 60 pages to explain, and it references a number of equally complex theorems and proofs.

This is interesting, because it means that very few, except some of the most advanced specialists in the field, will be able to understand the proof by themselves. Instead, the vast majority (including the vast majority of scientists) will accept the conclusion of a very small number of people regarding the validity of the proof. And since understanding the proof is so difficult, it may very well be that even the most experience mathematicians will be reluctant to draw very clear-cut conclusions.

Sometimes, clear-cut conclusions can be drawn. When I was a student, another student made the local news by announcing he had a proof of Fermat’s last theorem. We managed to get a copy of the paper, and shared that with our math teacher. He looked at it for about five minutes, and commented: “This is somewhat ridiculously wrong”.

However, In most cases, reaching such a definite conclusion is difficult. This puts us in the difficult position of having to trust someone else with better understanding than ours.

Understanding things by yourself

That being said, it’s always interesting to try and understand things by yourself. So I tried to read the summary of the proof. I don’t understand a tenth of it. However, the little I understood seemed really interesting.

If I can venture into totally bogus analogies, it looks to me like what Deolalikar did is build the mathematical equivalent of ice cube melting, and drew conclusions from it. Specifically, when ice freezes, phase change happens not globally, but in local clusters. You can infer some things about the cluster configuration (e.g. crystal structure) that were not there in the liquid configuration. In other words, the ice cube is “simpler” than water.

Now, replace atoms with mathematical variables, forces between atoms with some well-chosen Markov properties that happen to be local (like forces between atoms). The frozen cube corresponds to a P-class problem where you have some kind of strong proximity binding, so that you can deduce things locally. By contrast, liquid water corresponds to NP-class problems where you can’t deduce anything about a remote atom from what you learn about any number of atoms. Roughly speaking, Deolalikar’s proof is that if you can tell water from ice, then P and NP classes are distinct.

Of course, this is only an analogy, and it is very limited like any analogy, and I apologize in advance for totally misrepresenting Deolalikar’s subtle work. Nevertheless, I found the approach fascinating.

Crowds are stupid

Now, an alternative to personal understanding is to trust the crowd. Democracy. Unfortunately, if Slashdot is any indication, this doesn’t work at all.

Slashdot has a moderation system, where people vote for comments they find “Interesting” or “Insightful” or “Funny”. You’d think that this would let good comments rise to the top. But what really happens is that people with “moderation points” apparently feel an urge to moderate as quickly as they can. So the very first comments get moderated up very quickly, and drown any later comments in the noise.

Here are some of the comments on the P vs. NP announcement that Slashdot thought were “good”:

  • P is not NP when N is not 1 (“Funny”)
  • A random series of totally uninformed opinions on the cryptography impact (“Interesting” and “Funny”)

There are a few relevant gems in there, like the opinion of a professor at MIT that the proof is not valid. That leads to another more serious analysis. But there are a few redeeming gems even on Slashdot. Still, it’s too bad you have to sift through mud to find them.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s