The One Million Dollar Question: P = NP?

In “An Essay on the Principle of Population”, published in 1798, Thomas Malthus argued that economic developments made possible by technological advances would not improve the quality of life for the population in general, because any efficiency gain in the production of goods would be immediately offset by an increase on the size of the population. The Malthusian trap, as it came to be known, is partially a consequence of the fact that population grows geometrically way while production means can only increase arithmetically. In Malthus words:

Assuming then, my postulata as granted, I say, that the power of population is indefinitely greater than the power in the earth to produce subsistence for man.

Population, when unchecked, increases in a geometrical ratio. Subsistence increases only in an arithmetical ratio. A slight acquaintance with numbers will shew the immensity of the first power in comparison of the second.

This difference between geometric growth and arithmetic growth is also the basis for one of the most fundamental open problem in mathematics.

To understand the difference, imagine that you sit in your car and, starting from a stopped position, accelerate at full throttle. After about 8 seconds (if you have a reasonable car, but not a Ferrari nor a Tesla) you will be doing about 60 mph and covered about 300 feet. Imagine now that your car is very special and is able to accelerate forever. In less than a minute and a half it goes at the speed of an jet plane, having covered about 9 miles. After 4 hours it will go past the orbit of Moon. But, even this quite remarkable car will take about five years to reach the nearest star, Proxima Centauri (if not subject to relativistic effects). The speed of the car grows in accordance with an arithmetic progression and the space travelled grows with the square of the elapsed time.

Imagine, now, another experience, to illustrate a different progression. Imagine that you pick a sheet of paper and fold it in two, obtaining a stack that has two sheets. Keep folding it, one fold per second, obtaining at each time, a stack with an height that is the double of the previous stack. After 10 seconds, the stack is about two inches thick. Keep folding and, after 20 seconds, the stack reaches the height of a 20 storey building. After 45 seconds, the stack reaches the moon and, in less than 70 seconds, it reaches Proxima Centauri.

These two experiences illustrate the difference between geometric and arithmetic growth, so well understood by Malthus. Mathematicians and computer scientists know very well the difference between these two types of growth, and know that geometric growth will always be faster, much faster, than arithmetic growth, and even faster than any power of arithmetic growth (the square, for instance).

At this point, the reader will say: that is all nice and well, but what does it have to do with the one million dollar question? As it happens, one of the most important open problems in science consists, exactly, in determining which problems can be solved efficiently (i.e., in time that grows only arithmetically with the size of the problem) and which ones cannot be solved efficiently (those that require time that grows geometrically with the size of the problem).

Imagine that you are given a map of Europe, with its 44 capitals marked together with the distances between them, and your are asked if there are two capitals that are apart more than 3000 miles. For a computer, or even for the reader, the answer is easy to find, by simply analysing all pairs of capitals (there are “only” 946 pairs) and checking the distance between each pair, with recourse to the table of distances or a map.

But suppose now that you are required to answer a different question: is it possible to visit all 44 capitals driving less than 12000 miles? It is very difficult to answer this question because you would have to experiment all possible orders for the visit, and compute the length of each of these trips. It so happens that the number of possible orders is vastly larger than the number of sheets of paper that reached the nearest star, in our previous thought experiment. Interestingly, however, it is very easy to verify a positive answer to this question. If you are given a specific order in which the cities should be visited it is fairly easy to compute the total trip distance, by adding each pairwise distance. The difficulty lies in the fact that it is very difficult to find the right order.

In Computer Science, we call P the set of problems like these, whose solution can be determined efficiently, in time that grows slowly with the size of the problem (arithmetically on the problem size, or with a power of the problem size). We call NP the set of problems whose solution can be verified efficiently. There may exist problems whose solution can be verified efficiently but not determined efficiently. The game of Sudoku may be one example of such a problem, since our intuition tells us that it is easy to verify a solution but hard to find it. The problem of finding the shortest path to visit to a given set of cities (it is called the Traveling Salesman Problem) may be another of these problems. We also know that some of these problems (including these two) have an additional characteristic: if one of them can be solved efficiently, that solution can be adapted to solve any other problem in NP. These problems are called NP-complete.

The challenge resides in the fact that no one has ever managed to demonstrate that there exists a problem whose solution can be verified efficiently but cannot be found efficiently. Such a problem would be in NP, but would not be in P. If none of these problems exists, then P = NP, and the set of problems whose solutions can be verified efficiently and the set of problems that can be solved efficiently are exactly the same. If one of these problems exists, then P is not equal to NP, and there are problems that are very hard to solve, but whose solutions are easy to verify. On the other hand, to prove that P = NP, it would be enough to find a solution for any NP-complete problem (e.g., the Traveling Salesmen Problem). Such a solution could be adapted to solve efficiently any problem in NP.

Determining if P is or is not equal to NP is one of the most important questions in mathematics and in computation, and is one of the seven millennium problems, for which solution the Clay Institute offers a one million dollar prize. Of these seven problems, only one (the Poincaré conjecture) was solved until today. The solution is due to Grigori Perelman, a Russian mathematician, winner of the Field Medal (considered, by many, to be the Nobel Prize equivalent, for mathematics) who, after finding the solution, decided not to claim the prize.

Any one who is able to prove either that P = NP or that P is different from NP will be able to claim this prize. But, unlike other millenium problems, the resolution of this problem will have many practical consequences. If N is equal to NP, it will be possible to create programs that will solve complex and important problems efficiently, such as finding new cancer drugs or developing Artificial Intelligence systems. On the other side, privacy on the Internet will become much harder, because all cypher systems currently used will become vulnerable.

On the other hand, if P is different from NP, the solution of some problems will remain forever unreachable, even for the most powerful computers, even for quantum computers. Many questions in Artificial Intelligence, in biology and in many other domains will be harder or even impossible to answer, and we will never have the answer for many questions formulated by science.

Although no one has ever identified one single problem that is in NP and not in P, the majority of computer scientists believes that P is not equal to NP. Maybe the mathematical tools to address and solve this problem have not yet been developed, and it may take centuries to create them. It may even happen that this conundrum will remain an open problem forever. In a world where everything changes so rapidly, it is interesting to know that there are mathematical questions, deep and important, which remain open in defiance of human intelligence.

The original version of this article was published, in Portuguese, in the Público Newspaper. Picture by Jonathan Joseph Bondhus, available at Wikimedia Commons.