What is P versus NP?

Kevin Wang

In 2000, the Clay Mathematics Institute published the Millenium Prize Problems. These were seven mathematical problems, and solving any one of them came with the award of one million dollars. However, they were also some of the most complex, unsolvable problems of the past few centuries. Many appear intimidating just from their name—the Riemann Hypothesis, the Yang-Mills Existence, and Mass Gap, just to name a few. The very first problem on the list, though, looks easy enough, almost like a middle school algebra equation. It is simply titled “P = NP.” 

It is now 2021, and the P = NP problem has yet to be solved. Why is this so? What is it about this statement that even the greatest mathematical minds of the last two decades cannot solve it?

The actual meaning of the P = NP problem is much more complicated than it appears. It is a statement about different types of problems, or tasks. In computer science, a problem is anything you can get a computer to do, such as printing out a series of numbers, calculating an expression, or searching the internet. The solutions to these problems are called algorithms, and the field of computer science is heavily concerned with something called algorithmic complexity—how long it takes for an algorithm to run and a problem to be solved. However, this isn’t simply measured in seconds or minutes, but rather in relation to the number of elements an algorithm must operate on.

Take, for example, an algorithm that must sort a list of unordered numbers. It makes sense that the more elements, or numbers, there are, the longer this algorithm takes to solve the problem. Scientists have devised clever algorithms such as Merge Sort that are able to sort the elements in O(logn) time, meaning the runtime is proportional to log(n), with n being the number of elements to be sorted. 

The logarithm function. As n (the number of elements) increases, log(n) (the time required) increases, but at a decreasing rate. As a result, very, very large lists of numbers don’t require too much time to be sorted.

However, other problems have significantly larger complexities. Prime factorization, or reducing any integer down to the product of prime numbers, doesn’t sound too difficult. However, the most efficient existing solution is O(xn), or proportional to an exponential function. This grows much faster than the log function, and as n gets very large, the runtime will skyrocket.

The exponential function. As n increases, xn begins to increase very quickly. The algorithm quickly reaches a very long runtime.

A threshold used for algorithmic complexity is polynomial time—that is, whether an algorithm runs in O(nx) for some x. This is clearly a faster growth rate than logarithmic or even linear functions, but much slower than other functions such as exponential or factorial functions, regardless of the base x.

This is where P = NP comes in. P and NP are both sets of problems—essentially, just groups. P stands for “polynomial time” and NP stands for “non-deterministic polynomial time.” Specifically, a problem in P is something that can be solved in polynomial time—whether the best possible algorithm to run it on is at most polynomial. A problem in NP is something that can be verified in polynomial time—given any solution, how long it takes to make sure that that solution is correct. The question of P = NP asks if these two sets are equal—in other words, if every problem that can be verified in polynomial time can also be solved in polynomial time.

This distinction is important. The prime factorization is one such example. Verifying a given solution is extremely easy, and can be done in far less than polynomial time — simply multiply together all of the factors and check that it yields the correct number. Solving the problem, as we have seen, has yet to be done in polynomial time. However, we have yet to actually prove that this is the best possible solution to prime factorization. Therefore, we are certain that prime factorization is in NP, but we are uncertain if it is in P. In order to prove P = NP, we would need to prove that every problem in NP is also in P, and vice versa. This appears unlikely, but no one has formally proved that it is either true or false.

Why do we even ask this problem? Proving P = NP (or the opposite) would have important implications for different fields. For example, in cryptography, the study of making code and passcodes, most solutions and codes are easy to verify once you know the code. However, if we proved that P = NP, then that would mean that these codes are solvable in less than polynomial time — meaning someone could figure out your email password without too much time. Solving P=NP would have important effects in many fields, from algorithm development to biology. 

However, after decades, we have yet to solve the problem, and it doesn’t look like we’re getting any closer. Perhaps this question will always remain a mystery.

​