Programmers in the early days of computing started to solve problems using their cabinet size computers. Just like every solution initially, it used to be slow and then improved iteratively. But for some problems they cannot figure out a faster solution while a variety of problems have been proved to have no faster solution, like predicting the optimal move in chess. In order to handle the situation, researchers started sorting programs on how fast the program can solve the problem. Multiplication, Sorting have a faster program while for chess there is no faster program. But there were some problems which couldn’t be determined in which bucket they fell — finding prime numbers, travelling-salesman problem etc. This is where P and NP come in.
But how to figure out that the program is fast in general? Computer Scientists calculate the time for each step and add up. The catch is, they don’t answer this in minutes or seconds, instead they calculate it relative to the number of elements.
P class of problems are those which can be solved in polynomial time, or the set of problems whose solution time is proportional to polynomial. Obviously, an algorithm whose time is proportional to N3 is slower than N2 but this is insignificant when compared to another distinction — the complexity of algorithms where a number is raised to the Nth power, like, 2N. And this discrepancy gets much, much worse as N grows.
NP — Nondeterministic Polynomial time — is a problem whose solution can be verified in polynomial time. But many of these problems take exponential times to get solved. So what’s the deal with P equal NP? It means if the solution to a problem can be verified in polynomial time, can it be found in polynomial time? Frequently called the most important problem in the computer science domain, P vs NP is one of the 7 problems for which the Clay Mathematics Institute will give you million dollars to (dis)prove.
Did you ponder? There is no specific problem but there are multiple problems in this class. What does that mean? In early 70’s complexity researchers realised that a dozen NP problems they were struggling with are essentially the same but with some polynomial time constraints. You just need to prove one of the problems to make the entire NP set lie inside the P class set. As hard as it is to prove this problem, proving any problem in itself is a NP problem.
What makes it so important? The excitement to solve this problem is as vivid as the applications it can solve. A lot of the puzzles we are trying to figure out will become easier — the protein folding problem, drug for cancer. We can develop an accurate financial forecasting model, figure out the optimal arrangement of transistors on a silicon chip and the banking system might collapse as encryptions will become easier to crack. As Scott Aaronson said,