Originally published in the 3rd issue of the Warwick Engineer.
The question “Does P=NP” has been puzzling mathematicians and computer scientist since 1956 when Kurt Gödel wrote a letter to John Von Neunmann asking weather a certain problem could be solved in either quadratic or linear time. However, the precise formulation of the P versus NP problem was provided only in 1972 when Stephen Cook published the paper “The Complexity of Theorem Proving Procedures.” Often called the most important unsolved question of theoretical computer science, the P vs NP problem is one of the seven Millennium Prize Problems which the Clay Mathematics Institute – a private and non-profit organisation – will pay one million dollars for proving or disproving. Broadly speaking, P indicates the set of problems that are relatively easy to solve, while NP is the set of problems that are extremely difficult to solve. Thus, if P=NP then those problems which were deemed very hard, could have an “easy” solution. Howbeit, the situation is more complex than this.
When considering a particular problem together with a specific algorithm which is supposed to solve it, a common question that one can ask himself is: how long does it take to run the algorithm and therefore, solve the problem? Now, the layman would answer this question in terms of seconds, minutes or days for instance, however, computer scientist like to express the answer in terms of how many elements the algorithm has to handle. Let me give you an example. If you want to sort a list of N numbers in ascending order say, then the algorithm surely needs to look at each element in the list at least once. Yet, if it keeps track of the largest number seen so far – whilst going trough the list – then the algorithm needs to look at each element exactly once. As a consequence, we say that the execution time of the algorithm is directly proportional to the number of elements in the list – hence N.
Of course, there are different ways to solve this kind of problem which can have execution times slower or faster than the example given above. For instance, the execution time could be proportional to N2 or (2N3 + 1). Nevertheless, all the problems that can be solved by algorithms which have running time proportional to a polynomial expression – i.e. to an expression which can be written in the form where
is a sequence of real numbers and N is the input size of the algorithm – are said to belong to the polynomial class which is what the P stands for in “P =NP”.
NP problems – here NP stands for Nondeterministic Polynomial Time – on the contrary, are those problems whose solution can be verified yet not found in polynomial time. An example of this would be prime factorisation: how easy is to check weather a prime decomposition is right? Well you just need to multiply the numbers out and see if it gives you the correct number. Conversely, finding a prime factorisation for any number is known to be a very computationally expensive task. As a proof to this, in 2009 Thorsten Kleinjung et al. have successfully factored a 232-digit number utilising hundreds of machines over the course of two years.
So you might ask: “is there such a big difference between a polynomial and a non-polynomial running time?” Take this example: if an algorithm whose running time is proportional to N takes a second to run given N=100, then one whose execution time is proportional to N4 takes about eleven days to execute. Nevertheless, this is nothing compared to an algorithm whose running time is proportional to 2N – note this is an exponential expression – which in this case would take 300 quintillion years to reach an end.
As a consequence, asking “does P = NP” translates to: if a solution to a problem can be verified in polynomial time, can that same solution also be found in polynomial time?
There have been countless many attempts to solve this problem and there are scientists who still think that actually P does equal NP. Nevertheless, the majority out there are of the opinion that if this question shall ever be answered, then the answer would be that P ≠ NP.
Providing a proof for this problem would not only deepen our understanding of theoretical computer science and mathematics, but also improve or compromise many aspects of our life. Take for example the RSA cryptographic scheme, which is nowadays used for making internet transaction safe. The key principle behind this scheme is the practical difficulty of factoring the product of two very large prime numbers, which means that if P=NP, and if therefore there exists an algorithm which can carry out prime decomposition in a polynomial time, using this kind of cryptography would be totally useless.
All in all, I would like to live you with a deep philosophical question which was first posed by Scott Aaronson:
“How could such a clear mathematical question—a question about finite machines and problems, a question of great importance for science and industry—be forever unanswerable?”
Oh and, if you feel brave enough to attempt this question remember that in order to prove that P = NP all you need to do is to find one problem which has been proven to lay in NP and solve it in polynomial time. One single example which would change the face of science forever.
Marco Del Vecchio 