## 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.

## The woes of the "One laptop per child" project

Ivan Krstić writes in Sic Transit Gloria Laptopi about the woes of the One Laptop Per Child (OLPC) project.

The whole essay is a bit long, but definitely worth reading. It goes through the history of the OLPC project (including its roots in early experiments), through musings about the best choice of operating system, to suggestions on how to move the project forward successfully, after what appears to have been a severe crisis.

No matter what, Krstić is right that the whole experience will not have been in vain. But it’s too bad that a project like this can die for purely political reasons. On one hand, OLPC could not have seen the light of day without the efficient support of someone like Nicholas Negroponte. On the other hand, if we are to trust Krstić earlier essay, Things to remember when reading news about OLPC, he’s now almost a liability to the project:

To those on the outside and looking in: remember that, though he takes the liberty of speaking in its name, Nicholas is not OLPC. OLPC is Walter Bender, Scott Ananian, Chris Ball, Mitch Bradley, Mark Foster, Marco Pesenti Gritti, Mary Lou Jepsen, Andres Salomon, Richard Smith, Michael Stone, Tomeu Vizoso, John Watlington, Dan Williams, Dave Woodhouse, and the community, and the rest of the people who worked days, nights, and weekends without end, fighting like warrior poets to make this project work. Nicholas wasn’t the one who built the hardware, or wrote the software, or deployed the machines. Nicholas talks, but these people’s work walks.

Makes you wonder who really “invented” the OLPC… Two earlier posts may be relevant to this topic:

- Another earlier discussion of Group Dynamics, which seems to apply quite well here
- Maybe we should hear the other side of the story.

## How To Teach Special Relativity

*How to Teach Special Relativity* is a famous article by John Bell where he advocates that the way we teach relativity does not give good results. He describes an experiment now known as Bell’s spaceship paradox (even if Bell did not invent it):

In Bell’s version of the thought experiment, two spaceships, which are initially at rest in some common inertial reference frame are connected by a taut string. At time zero in the common inertial frame, both spaceships start to accelerate, with a constant proper acceleration g as measured by an on-board accelerometer. Question: does the string break – i.e. does the distance between the two spaceships increase?

#### Considered a difficult problem

The correct answer is that the string *does* break, even if the spaceships appear to always be at the same distance from one another as seen from an observer who did not accelerate with the spaceships. Yet, according to Wikipedia:

Bell reported that he encountered much skepticism from “a distinguished experimentalist” when he presented the paradox. To attempt to resolve the dispute, an informal and non-systematic canvas was made of the CERN theory division. According to Bell, a “clear consensus” of the CERN theory division arrived at the answer that the string would not break.

In other words, this problem was considered *hard* by a majority of serious physicists at the time Bell raised the question in 1976. I would venture to say that this remains the case today, except that this particular paradox is probably well known now. But the teaching of special relativity has not changed. This is how we explain the paradox today. I have a lot of admiration for John Baez in general, his “blog” is even in the sidebar of this one. But with all due respect, the explanation of the paradox posted on his web site is utterly *complicated* (I know he gives credit to someone else for it, but by hosting it on his web site, I would say that he condones it).

#### It should be easy

This particular formulation of the paradox was not known to me until someone recently asked me if the string would break. Using my little technique, it took me less than one minute to have the correct answer, without looking it up, obviously, but also without any computation or complicated diagram. Here is the mental diagram I used (click to see it in high resolution):

On this diagram, time is represented horizontally, and the two space ships are represented by the green and red curves, which are identical but separated by a distance along the vertical “spatial” axis. The distance at rest is represented by the blue arrow. The distance as measured between the two ships after they started moving is measured by the green and red arrows. The distance as measured “from the ground” is along the vertical axis, and remains constant.

Remember the only trick is that a “cosine” contraction on this diagram corresponds to a dilatation in relativity and conversely. On the diagram, the red and green arrows are obviously shorter than the blue arrow. The contraction factor is the cosine of the angle between these arrows and the vertical (space) axis, which is the same as the angle between the red or green curve and the horizontal axis. Therefore, relativity predicts that the distance between the two ships, as seen from the ship, will *increase*. Specifically, it increases by a factor usually denoted “gamma” (but which I prefer writing as the cosine of an angle myself), which can also be seen as a hyperbolic cosine, and which plays in Minkowski geometry the exact same role as the cosine in the Euclidean diagram above. You can find the precise mathematical relationship here.

Consequently, the string *will* break.

#### Accelerated solids in relativity

Another interesting observation one can make from the diagram is that you cannot draw a straight line that is perpendicular to both curves. What is “space” for one ship is not just “space” for the other. You need to draw a curved line between the two rockets if you want to always be perpendicular to the local “time” direction. In other words, the “time” direction for the string is not constant along the way, so all parts are *not moving at the same speed*. Someone sitting anywhere on the string will see other parts of the string move relative to him. That’s another way to explain why the string will break.

You can easily verify that this problem exists for any kind of accelerated solid. All parts of an accelerated solid in special relativity do not move at the same speed.

#### My own puzzle

Here is the interesting other thing that I realized within this short moment of reflection: there is a way for the two ships to accelerate “identically” (for a suitable definition of identically which remains to be given) so that the string will not break. Can you find it?

*C’est tout de même dur à avaler.Comment voulez vous qu’on enseigne cela à des élèves de Terminale?*

Jean-Claude Carrière, in

*Entretiens sur la multitude du monde*with Thibault Damour