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:
- Pull up gently on the shackle and hold it in place. Turn the dial clockwise listening carefully until you hear the lock click.
- 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.
- 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.
- The failure to break a lock does not mean that someone cleverer cannot break it.
- 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.
- 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?
So, since you raised the issue of crazy colonels:
1. What do YOU think about the request by your country to extradite Assange, based on some crazy laws, made by some crazy capitalists, and based on the utterly insane assumption that your laws apply outside of your territory, to a person who has nothing to do with your country except revealing the crimes of your crazy colonels?
2. What do YOU think about the threat made by your country to level Iran’s sacred sites?
3. What do YOU think about “containing Russia”, and the “Russian threat”, a country where the median salary in the regions is somewhere around 200-300 dollars a month?
So, what do you think about it all?
By textual analysis, since we raised the issue of crazy colonels, I’d say this is asked-and-answered, my friend.
It is one of my favorite movies. Ripper is a general not a colonel, however.
Dear Bill Moran:
Oops. Got confused about the ranks. Thanks for the catch. I must have got confused with Mandrake? It is indeed a terrific movie.
Best
Dick
A NL = NP proof:
https://doi.org/10.5281/zenodo.3355776
I wrote the paper that proved that the maximum independent set could be extracted using the eigenvalue interlacing theorem in polynomial time by removing the vertices. Now, I uploaded my work to ResearchGate on March 2, and it achieves 206 reads (73 Full-text reads) on March 6.
If you are interested in my work, please read my paper below,
https://www.researchgate.net/publication/339627657_Extract_maximum_independent_set_using_eigenvalue_relation?channel=doi&linkId=5e5d20efa6fdccbeba12d7c6&showFulltext=true
I rejected from STOC 2020 only review comment ‘doubtful.’ I doubt no researcher wants to read the paper that states P=NP in academia…
So, I rewrite the proof as simple and clear as possible I can and post to RG (I cannot submit to arXiv for no approval from other researchers).
Hmmm, at O(N^6) you can probably write the code and use it to solve max clique benchmark instances, the 125 vertices one might be solvable if you let the algorithm run for a few days or so, or at least verify it works with smaller instances and how long it takes.
Make sure your algorithm is correct, often with trying to improve upon the current best performance for algorithms, you run into issues where things don’t scale as well or the algorithm simply fails to produce correct results in some cases (things that look correct with N=10 vertices don’t work when N=20). Part of the rejection is probably because you provided only theoretical proof, with no implementation or proof that you have actually tested the algorithm and confirmed it works. I see pseudocode but no comparison of algorithms. At O(N^7), that is a lot of complexity and there are a lot of things that could go unexpectedly.
https://turing.cs.hbg.psu.edu/txn131/clique.html (Benchmark instances)
Nice P=NP allegory.
If you like to read a crazy idea about P=NP and you can bare the lack of rigour, try:
https://meaningofstuff.blogspot.com/2017/04/pnp-is-indecidable-conjecture.html
It might be obviously wrong or/and it might inspire a better idea. if you find an obvious flaw, please let me know with a comment. For anyone asks, I’m a programmer, not a mathematician 😉