To P or NP that is the question

On May 24th, 2000, the Clay Mathematics Institute (CMI) produced a list of seven problems called the ‘millennium prize problems’. These obstacles were increasingly difficult to solve as well as requiring a wealth of knowledge to even comprehend. Anyone who solved one of these problems would be awarded a million-dollar cash prize. Of these problems, P vs NP was the most recent to come about.

Since the creation of the Turing machine in 1936 by Alan Turing, the power of our computers has grown exponentially. Simple operations like multiplying numbers would take human computers days to solve while this took the original Turing machine only a couple hours. And nowadays, these problems can be solved instantly with the use of smartphones.

However, not all problems are created equal. While problems like addition and multiplication have become trivial, some problems have not scaled as well with the increase in computational power across the decades. Even with better algorithms we are still yet to find efficient solutions to several mathematical problems. This gave rise to the distinction between two classes of problems, ‘P’ and ‘NP’.

P defines all those problems solvable in deterministic polynomial time. This can be thought of as problems that are easy to solve and whose solution is easy to verify. For example, if given two numbers 3 and 5, multiplying these two can be done fairly easily.

(Polynomial is a function of n in the form 2n3 , 5n or 20n1000 however they are not exponential)

NP defines problems that are solvable in nondeterministic polynomial time. This means if a given machine could run all the possibilities in parallel, it would take polynomial or linear number of steps to compute each solution. Simply put, these are the class of problems that may or may not be easy to solve but easy to verify.

Take this number: 3763           

If I asked you to get its prime factors, what would you do? You may start at the number two and go through all numbers until you divide this into a whole number. With numbers with more digits, the number of steps dramatically increases and by extension the time required as well solve it.  However, if I told you the prime factors of this longer number, 356,809, were 509 and 701, how long do you think it would take to confirm my statement? One may bring out their calculator and calculate it themselves. This is the nature of an NP problem.

So, when we say a problem is easily solvable or verifiable, what does that really mean? This refers to how problems scale up with the size of the input. For example, given an 8×8 jigsaw puzzle with ambiguous pieces to solve, it may take a couple of minutes for a person to solve and a couple seconds for a machine, however, if given a 20 x 20 grid of ambiguous pieces, that becomes much harder to solve.

Using these definitions, P must be a subset of NP as any problem that’s easy to solve is just as easy to verify. If I wanted to see whether there was a solution to a problem, I could just compute the solution and tell you yes or no. This begs the question, ‘is the reverse true?’. Is every problem that’s easy to verify the answer to also easy to solve? Does P = NP?

Why is this problem significant?

Well, if P = NP, that would mean that every problem that you could guess the answer to could have a fast algorithm to determine it. The implications of this would be tremendous in today’s society, as seemingly overnight, problems once thought impossible to solve would become easy. Protein folding which would help us find cures to complicated diseases such as cancer, and the multitude of logistical issues spanning many fields would now become unproblematic. However, modern day cryptography (e.g. banking, RSA certificates in https) would be promptly made obsolete as a lot of it relies on that same factorization problem to keep data secure, we discussed earlier.

NP-complete refers to the hardest problems in the class NP to solve and serves as an upper bound on how hard problems in NP can get. That being the case, finding a polynomial time solution to any of these would find an efficient solution to all NP problems at the same time. An analogy would be if you could find a way to get a basket from one point to another across a river safely, then if you needed to do the same with an egg, you could simply put that egg in the basket and send your basket across the river.  This would prove P = NP. However, since no one has found a polynomial time algorithm for solving any of these problems, it is widely believed that P ≠ NP but no one is able to prove this either because proving P = NP is an NP problem in itself.

Complexity classes

 Although P and NP are the classes of problems given the most attention to, there is a whole biome of complexity classes which subsume each other. We are still unsure if some of these classes are the same. In any case, an answer to any of these questions will have immense real-world implications. If you’re interested in a million dollars as well, the prize is still available to the first person able to solve the P vs NP, in addition to the five remaining millennium prize problems.

Leave a Reply