Machines Like Me

by Ian McEwan

would have, in the words of the mathematician Stephen Cook, who formulated the problem in these terms in 1971, “potentially stunning practical consequences.” But what was the problem? I came across an example, an apparently famous one, that helped only a little. A travelling salesman has a hundred cities on his patch. He knows all the distances between every pair of cities. He needs to visit each city once and end up at his starting point. What’s his shortest route? I came to understand the following: the number of possible routes is vast, far greater than the number of atoms in the observable universe. In a thousand years a powerful computer wouldn’t have time to measure out each route one by one. If P equals NP, there’s a discoverable right answer. But if someone gave the salesman the quickest route, it could be quickly verified mathematically as the correct answer. But only in retrospect. Without a positive solution, or without being handed the key to the shortest route, the travelling salesman remains in the dark.