### The Golden Ticket: P, NP, and the Search for the Impossible

I have several books in my review stack, so that when the book by Lance Fortnow arrived the day before yesterday, I opened it for cursory inspection, just to get a first impression. Yesterday I finished reading it. It's a tremendously good read, entertaining and informative.

"P vs NP" is one of the seven millennium problems selected by the Clay Mathematical Institute as the most important challenges inherited unsolved from the twentieth century. One of these - the Poincaré Conjecture - has already been solved, the others remain open.

Lance Fortnow tells the story of the "P vs NP" problem - its emergence, attempts to solve, the significance of a solution, its repercussions whichever way it comes out. Of the seven problems, a solution to "P vs NP" will have the most profound, probably even evolutionary, effects on the human society.

"N" stands for a class of problems that we know how to solve (efficiently); "NP" describes a class of problems that we are interested in solving, but only know how to check whether a specific solution is correct or not. Colloquially speaking, "N" denotes what we know, "NP" what we want to know. The "P vs NP" problem asks whether the two classes are (potentially) the same. If

This is like solving Sudoku problems. There is a huge amount of them, each depending on the initial set of clues. To solve the "P vs NP" problem, an algorithm should be able to solve any of particular Sudoku problems, regardless of the initial clues, and regardless of their size; the algorithm should come with a proof that this is indeed so.

The "P vs NP" problem was conceived during the Cold War, independently on the two sides of the Iron Curtain. The book draws a picture of dramatic and unexpected developments "here" and "there"; the juxtaposition reinforces the view that it would be better for everyone if the two classes of problems were different.

There is (p. 81) a compelling anecdote how the famous Russian mathematician Andrey Kolmogorov saved the study of Probability Theory in Russia. According to Marxist philosophy, there are laws that govern every phenomenon in the world such that there could not be possibly independent events. Kolmogorov came up with an example of a priest who, during a drought, prayed for rain. Next day it rained. For the Marxist philosophers it was impossible to admit that a prayer might have helped, forcing them to accept that the prayer and the next day rain were two independent events.

For a problem being hard does not imply that even in special cases it may not have an efficient solution. There are ways and ways to tackle hard problems: solving a problem approximately, finding and adapting a solution to a close but different problem, speeding up computers, even inventing altogether new computing technology. Thus the book describes the novel field of research - quantum computing. Awfully exciting.

Many approaches have been tried to solve either way the "P vs NP" problem. Nonetheless, here is what the author had to say about the progress made so far (p. 121):

We are further away from proving

P ≠ NP than we ever were. Not literally, but in the sense that there is no loner any obvious path, no known line of reasoning that could lead to a proof in the near future.The only known serious approach to the N versus NP problem today is due to Ketan Mulmuley from t he University of Chicago. He has shown that solving some difficult problems in a mathematical field called algebraic geometry (considerably more complex than high school algebra and geometry) may lead to a proof that

P ≠ NP. But resolving these algebraic geometry problems may require mathematical techniques far beyond what we have available today.

This may be so; still, it is reassuring that another branch of abstract mathematics seems to find bearing on a problem of practical importance. Talk of The Unreasonable Effectiveness of Mathematics in the Natural Sciences.