R. J. Lipton in Gödel’s Lost Letter and P = NP:
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.
More here.