The theory of computation emerged powerfully in the 1930s, when Alonzo Church (1903-1995) and Alan Turing (1912-1954) independently proved that the answer to Hilbert’s decision problem was negative. Posed by Hilbert in 1928, the problem asks: is there an algorithm that can decide in a finite number of steps whether a given formula can be proved from a given set of axioms?
The theory of computation is related to mathematical logic, and was pioneered not only by Church and Turing, but also by Gödel himself, von Neumann and Claude Shannon (1919-2001). Due to the growing importance of computers in the modern world, computational problems are among the most relevant problems facing mathematicians today; and the most relevant of all is to determine whether or not the so-called classes P and NP are equal – usually written as “P=NP?”.
Grosso modo, a problem is said to be of class P if there is an algorithm that solves it in polynomial time of the number of data. In an NP problem, we do not know whether a solution is possible in polynomial time of the number of data, but if we are given a solution, then it is possible to prove in polynomial time of the number of data that it is indeed a solution – of course, all these imprecise definitions can be specified in a completely satisfactory way using formal logic. A typical P problem is that of calculating the greatest common divisor of two numbers; Euclid’s algorithm, for example, solves the problem in a time of the order of the square of the number of digits in the numbers. A typical NP problem is that of finding the prime factors of a number; nowadays we do not know how to solve this problem in polynomial time – which does not mean that it cannot be done – but if we are given the factors of the number, checking that they are indeed the factors requires only their multiplication – which can be done in a time of the order of the square of the number of digits in the numbers. The importance of factoring a number in polynomial time is key to the security of electronic communications based on RSA cryptography, whose security is based precisely on the fact that there are currently no known time-efficient ways of finding the prime factors of a number. This may give an idea of the importance of deciding the solution to the problem P=NP?
The same importance of mathematicians could be evaluated if we know the solution of the problem P=NP? Indeed, proving the correctness of the mathematical proof of a theorem is a P-type problem. Searching for the proof of a theorem is such a complicated problem that it is not even NP, but we can do the following; given a polynomial \(p\), we call \(I_p\) the set of theorems that admits a proof of length bounded by that polynomial in the number of symbols necessary to state the theorem. For every polynomial \(p\), checking whether a theorem is in \(I_p\) is an NP-problem. So if the class of problems P were equal to NP, and the proof were sufficiently constructive, for every polynomial \(p\) there would exist an algorithm that in polynomial time would allow us to find a proof of every theorem in the set \(I_p\). If that were so, one would be tempted to say that we mathematicians would have lost much of our usefulness.
The P=NP? problem is one of the seven millennium problems, for the solution of which the Clay Institute is offering a million dollars.
The Clay Institute was founded in 1998 by Boston tycoon Landon T. Clay. On the occasion of the commemoration of the year 2000 as the world year of mathematics, the Clay Institute selected the seven unsolved challenges it considered most fundamental to mathematics, and pledged to pay one million dollars to anyone who solved one of them. The challenges included the Poincaré conjecture and the Riemann hypothesis – the only ones that all of the mathematicians consulted included on their lists – as well as P=NP?
The Clay Institute’s initiative imitated that of David Hilbert in 1900, when he proposed a list of 23 problems which, in his opinion, were the most important challenges facing mathematics in the 20th century. Hilbert was not a millionaire and did not offer money, neither much nor little, to anyone who solved any of these challenges. “Money is a mighty gentleman”, wrote our Quevedo, but Hilbert knew that, when a mathematician decides to spend his brain cells looking for the solution to a deep and difficult problem, it is not money that he is looking for. So it is not at all clear that the Clay Institute’s reward will speed up the solution of the seven Millennium Problems; or perhaps we should say that it is very clear that it will be of little use, if we consider the utter disdain Perelman showed when he turned down the million dollars he was entitled to after solving the Poincaré conjecture – the only one of the seven Millennium Problems that has so far been solved.
References
Antonio J. Durán, Crónicas matemáticas, Crítica, Barcelona, 2018.
Magnífico artículo del profesor Antonio J. Durán. Gracias