P=NP: A Story

The P=NP story without symbols.

[ The Movie ]

Dr. Strangelove is the classic 1964 movie about the potential for nuclear war between the US and the Soviet Union during the cold war. The film was directed by Stanley Kubrick and stars Peter Sellers, George Scott, Sterling Hayden, and Slim Pickens.

Today we try to explain the P=NP problem in an “analog” fashion.

In Dr. Strangelove, US President Merkin Muffley wishes to recall a group of US bombers that are incorrectly about to drop nuclear weapons on Russia. He hopes to stop war. Here is the conversation between General Turgidson played by Scott and Muffley played by Sellers, in which Turgidson informs that the recall message will not be received…

Turgidson: …unless the message is preceded by the correct three-letter prefix.

Muffley: Then do you mean to tell me, General Turgidson, that you will be unable to recall the aircraft?

Turgidson: That’s about the size of it. However, we are plowing through every possible three letter combination of the code. But since there are seventeen thousand permutations it’s going to take us about two and a half days to transmit them all.

Muffley: How soon did you say the planes would penetrate Russian radar cover?

Turgidson: About eighteen minutes from now, sir.

This is the problem that P=NP addresses. How do you find a solution to a problem that has many potential solutions? In this case there are over thousands of possible combinations. Since each requires sending a message to an electronic unit that sits on a plane, thousands of miles away, and since messages cannot be sent too often, it will take much too long to find the secret message.

The central P=NP question is: Can we do better than trying all possibilities? The answer is yes—at least in the case of the movie, the secret combination is indeed found. More on that in a moment.

Opening Mechanical Locks

In Dr. Strangelove the issue is finding the three letter code for a certain device that sits on the bombers. The protocol is: Send a three letter code to the bombers. If the code is correct, then the bombers will be recalled, and all is saved. If the code is wrong, then nothing happens.

Instead of this, consider the same type of problem for finding the combination to a mechanical lock. That is a lock that is often at a gym, for example, to protect your belongings. Recall you spin the lock’s dial three times to the right, stop on the first number, then turn one time to the left, stop on the second number, and finally go to the right to stop at the third number. Then you pull the lock open.

This works provided you know the combination. In general there are 64,000 such combinations. So unless you know the numbers, you are in trouble. Trying all possible combinations is not possible for mortals. But there is hope. It is possible to find the combination without knowing it. This is possible provided: You have the combination lock in your hands.

If you only can send a possible combination to someone else to try, you are out of luck. Unfortunately in Dr. Strangelove the device on the bomber is not in your hands. So as the General says, we are trying all the possible combinations one at a time. But if the device is local you can do better.

Breaking The Locks

There are many sites on the web that explain how to do much better. Here is one way to find the first number for a lock:

1. Pull up gently on the shackle and hold it in place. Turn the dial clockwise listening carefully until you hear the lock click.

2. Start with a good deal of pressure and gently let up as you spin it around, until you meet resistance in only one place. It should catch in only one place, making a click.

3. Add 5 to that number and write it down.

This is the first number in the combination. There are similar methods to get the remaining two numbers. But already you have reduced the choices for the combination from 64,000 by a factor of 40. The rest of the how-to-do rules help you get the remaining two numbers.

Note this attack relies on physical properties of the lock. A lock is made from springs and gears and rods, and is not perfect. As you turn the dial the mechanical parts rub and make noises. These noises reveal information, that is useful to you. Information that can reveal the combination of the lock.

Opening Digital Locks

The point is that there is a way to open a lock without knowing the combination. Here the trick is that you can try and use the lock and play with it in a way that it reveals information about its secret combination. This is what the P=NP question asks:

Are there ways to manipulate a digital lock and get it to reveal information?

Put another way: Do digital locks make noise?

Essentially P=NP is true if digital locks all are imperfect, like mechanical locks. That is, if digital locks all make noise. It is widely believed that is false. The belief is that P NP which means that there are essentially perfect digital locks. That is some digital locks make no noise.

P NP

Why is it believed that digital locks can be perfect? Well the answer is simple. To date certain types of digital locks have not been broken. That is no one yet knows how to make them click and reveal information. This is of course a dangerous position for several reasons.

1. The failure to break a lock does not mean that someone cleverer cannot break it.

2. There are reasons that if some people knew how to break certain digital locks that they would not tell anyone. They might prefer to keep their ability secret to make money or cause harm.

3. Finally, it seems dangerous to guess that anything can be done without noise.

The latter point is that making systems work perfectly is usually impossible. Mechanical systems must have friction of some kind, and it seems possible that digital systems will also. We will see.

Smart Search

Colonel Ripper, played by Hayden, is the one that launched the bombers against Russia. The recall code is found and the bombers are recalled. An officer named Mandrake, played by Sellers too, notices some doodles on a pad by the crazy Ripper. It is covered with an interlocking pattern of the words Peace On Earth, and Purity Of Essence. Ripper is obsessed with these ideas—do not ask why.

Mandrake: Peace on Earth. Peace on Earth. Peace on Earth: P O E. Purity of essence. O P E. (whispers) O P E.

This is the key. This information is sent to the Pentagon and soon the bombers are recalled. The search space is cut down from thousands to 6 possible orders. Success. Well if you’ve seen the movie, you know it was not exactly success, but that failure has nothing to do with our attempt to explain the P=NP question.

This second idea is different from whether locks make noise. It is whether every lock has a giveaway by dint of the process by which we obtained that particular lock to begin with. Note that the lock is not the definition of the problem itself, like SAT or graph 3-coloring, but rather a particular instance of the problem. We have discussed how instances of factoring that tend to be generated by algorithms have collective giveaways in an earlier post—which quotes another part of Dr. Strangelove.

Open Problems

I love the movie Dr. Strangelove, and love any excuse to talk about it. So please forgive me this story about P=NP. I hope that trying to understand the P=NP question without complex notation may help us better understand it. What do you all think?