The Clay Mathematics Institute released ‘The Millennium Problems.’, a set of 7 problems each awarding a million dollar prize to anyone who manages to solve it. Only one of them has been solved till date. The easiest one of them to understand, without having profound knowledge in mathematics, is the P vs NP problem. So let me break it down for you without it making you break down.
It all started in 1971, when Stephen Cook introduced the world to the P vs NP problem. Computer Science was in its early stages and scientists were playing with programming on their retro, cabinet sized computers to solve real world problems with stunning speed. The P vs NP problem is a huge part of computer science but also impacts us in a fundamental way. How so? Because all of computer science algorithms come through human problem solving techniques. And right there is the hitch. The P vs NP problem can take the whole idea of problem-solving to completely new and unimaginable levels.
Computer scientists are usually obsessed about a term called ‘time complexity’; and they should be. It tells us how much time the computer will take to solve a problem. And we need to do it fast. The easy methods of solving things are sometimes really slow, but usually some genius comes along and does it in a faster way. But still all the problems couldn’t be categorized fully.
The Travelling Salesman: A brutally painful computer science reference by : https://xkcd.com/
Let’s look at this in a way that everyone can understand. Consider a simple multiplication problem, 23 multiplied by 5. One can easily get the answer 115 just by carrying out the multiplication. This is a problem in which the solution can be easily obtained by directly solving it. But if I ask you to tell me the solution to a chess game, you can’t. Because it is too complicated and a single solution does not exist.
Now consider a Sudoku game. Sudoku, in itself is a challenging puzzle and it would take a person some amount of time to solve it. However, if provided with the solution directly, it can be easily verified to be the correct one. Thus, our second type of problem is the ones which take a long time to solve, but its solution can be checked in short while. This analogy can easily be put in for P and NP.
Okay Spoiler Alert! The next paragraph is a bit math-ish. Meaning if you don’t like math – Its BORING – just skip it; its fine I won’t mind. You won’t miss anything, I just couldn’t help sneaking in some technical terms.
Easily solvable problems like multiplications are ‘P’ while the ones which cannot be solved easily but verified in a short time are called ‘NP’. It is called P as it can be solved in polynomial time of number of inputs ‘n’, meaning that the time required is given by an equation containing n, n2, n3 etc. NP however has exponential terms like 2n. Hence, it takes a longer time. But its verification takes polynomial time. All P are said to be a subset of NP, but there are multiple divisions inside and outside NP.
Okay, enough technicalities, let’s get down to business. Why is this a million dollar problem? Amazingly, scientists believe that all problems must have a faster method to solve, if it can be verified fast.
But they haven’t been able to solve them fast! So we don’t know if P=NP, but neither do we know if P is not the same as NP.
Here’s the catch, if someone tells us how to get an NP problem solved fast, a similar way can be implemented to solve all NP problems fast. This will also prove that NP=P. That means, if we get a solution we can verify P=NP easily. But it is an extremely difficult to solve it. How ironic! P vs NP is itself an NP problem. So solving P=NP is basically …….. solving P=NP. An interesting loop is created here and thinking too much about it just hurts the brain.
After this anti-thesis was revealed, most of the scientists began to think that P is not the same as NP and there do exist problems which we cannot solve easily, or at all. If the sheer complexity of the problem doesn’t motivate mathematicians to pursue this, there are a lot of perks that come along with solving NP problems faster.
Protein folding, task scheduling and traffic routing are all NP problems. Solving this would make machines work faster, economies develop faster, prevent traffic jams forever and even cure cancer! These are amazing incentives to solve this problem but the negative effects are really dangerous.
Any idea of privacy or protection like cryptography and encoding become completely useless. Why? Because cracking passwords is an NP problem. Cracking a password on your own is very difficult, but if a password is suggested as the answer, its easy to check it. So there would be an ultra fast way to hack a password in seconds. This changes the way we live our lives. Imagine if checking the answers to your objective test was the same as solving it!
If anything, this mathematical equation actually has philosophical consequences all over it. Scott Aaronson, a former MIT researcher, famously quoted that if P=NP there would be “no fundamental gap between solving a problem and recognizing the solution once it’s found.” which would mean “Anyone who could appreciate a symphony would be Mozart.” And truly, this actually sounds a bit absurd because it changes the whole nature of solving any problem.
Scientists are still debating over this one and Clay Institute’s offer is still on the table. The field of computer science is barely 70 years old and it is very young compared to the rest of the sciences. There are many more advancements to come and this provides an exciting gateway into making a lot of things possible and making some groundbreaking discoveries. All in all, the most obvious thing and the most confusing thing to say about P vs NP, is that “you have it to solve it to solve it”.
A quick illustration of the NP set by my all time favorite comic page: https://xkcd.com/
So there it was, the P vs NP, which was the most easiest problem to understand in all the Millennium problems. And probably the most difficult one to solve…. I don’t know, only one has been solved till date. If you stuck with me till the end of this, I think you are ready to face the other ones.