Sign in

To P or to NP, that is the question

The P vs NP problem, often called the biggest unsolved problem in theoretical computer science, in it's simplest form asks - "Whether every problem whose solution can be verified quickly, can also be solved quickly". Belonging to one of the seven Millenium Problems put forth by the Clay Mathematical Institute, it carries a price of 1 million US Dollars for the first person to solve it correctly. In fact, it is so famous that it even has a movie on it aptly called "Travelling Salesman". Let's see if you can be the winner of those 1 million Dollars.

The term "quickly" used above translates to a problem being solved in polynomial time by a computer, for example n^2 or n^5, where n is the number of inputs. So the class of problems that some algorithm can solve in polynomial time, is called "P". On the other hand, the "slow" problems are those that a computer solves in exponential time, for example 2^n or 5^n, where n is again the number of inputs. Although, the trick with these problems is that they can be verified in polynomial time. This class of problems is called "NP". A real life example of an "NP" problem is something you probably see everyday: Sudoku.
An answer to the "P vs NP" problem would answer if problems that can be verfied in polynomial time can also be solved in polynomial time. The problem is to actually prove or disprove that the classes P and NP are equal, i.e. P = NP. This would mean that problems that are considered "hard" actually have "easy" solutions.
Before looking further into the problem, let us look at the implications of the solution of the problem and why is it even a problem anyway, let alone the biggest unsolved problem in theoretical computer science. The most important impication would be for the field of cryptography, as almost all cryptographic algorithms that secure passwords and financial data and government secrets rely on P not being equal to NP. If this was not the case, all encryption would be relatively easy to break and all the protections of we enjoy in the virtual world would be moot.
But there are also positives to proving P equal to NP. The problem of protein folding is an NP problem and if it was proven to be a P problem, humanity could cure cancer. A lot of computational complexity researchers believe that P does in fact, not equal NP. In 2002 William Ian Gasarch conducted a poll among researchers regarding the "P vs NP" problem and it revealed that people's confidence believing P does not equal NP is increasing, it was 62% in 2002, then it rose to 83% in 2012 and 89% in 2019. In 2019, when only subject experts were polled, 99% believed P does not equal NP.
There is also concensus on the fact the current concepts and proof techniques that are available to us are not powerful enough to decisively prove or disprove that P equals NP and that there exist concepts and proofs that we are not yet familiar with that will be required to answer the question.
To quote Scott Aaronson, a computational complexity researcher from MIT, "If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffet." One of the most beautiful things that have arisen around the debate if P equals NP, according to Micheal Sipser Michael Sipser,head of the Department of Mathematics at MIT and a member of the Computer Science and Artificial Intelligence Lab’s Theory of Computation Group, is that it has helped bridge the gap between the mathematics and the theoretical computer science communities.
But why is it the most famous problem in theoretical computer science, to understand that, consider this example. You are given a task to sort a list of numbers. You take the easy route and do it using Bubblesort. It gets the job done, but is not very efficient. Later your list of numbers becomes so large that Bubblesort doesn't cut it, so you're forced to implement a more efficientalgorithm, like Mergesort. See, the problem didn't change, but the second time around, the solution was just faster and more efficient.
Similarly, some problems that were thought to be solvable in exponential time, were proven to be solvable in polynomial time, that is, some NP problems were actually proven to be P problems. But doesn't that mean that P is equal to NP? Actually it doesn't. The classes of problems like P and NP aren't seperate from each other and are more like sets and subsets. The class of P problems is actually a subset of the class of NP problems. This is beacause not all problems in the NP class take the same amount of time to solve, it's just that all of them can be solved in exponential time or less. So problems in P can obviously also be problems in NP.
A special class of problems in NP, called NP-complete problems and these problems are the hardest and most time consuming of all problems that belong to the class of NP.
So while, some problems from the NP class have been shown to be in P, none of the NP-complete problems ever have been. So the question "does P equal NP" actually means can NP-complete problems be shown to be a part of the class P. So the name "P vs NP" is kind of a misnomer and the "NP" in "P vs NP" actually refers to NP-complete problems.

So all we're waiting for is someone to prove that just one of the NP-complete problems is a part of the class P, and if that someone is you, you could be Mozart, Gauss and Warren Buffet all in one.