CTK Insights

Tweet

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 P = NP, we get (and in a pretty swift order) everything we want (even if later on we may regret getting that). If P ≠ NP, solving difficult problems may require growing hardships, fresh insights and new technologies. It is reassuring to know that, by now, there is probably no one who believes that P = NP, but the fact is that no one knows for sure. Much of what is going on on the internet concerning security depends on the assumption that P ≠ NP. Many things will go awry if a proof is found to P = NP. However, in this case, the proof could not be of mere existence. To solve the problem one must supply an efficient algorithm for solving one of what's known as NP-complete problems, and prove that the algorithm will work regardless of the underlying data. Luckily, the NP-complete problems are among the hardest.

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.