P vs NP problem is one of the great unsolved problems in theoretical computer science. This problem has become broadly recognized in the mathematical community as a mathematical question because it is fundamental, important and beautiful. It is in fact one of the seven Millennium Prize Problems. If you solve this problem, you get $1 million and become really famous among mathematicians and computer scientists. If you are evil, then you can use your proof to become richer than God, then publish your proof, reject the prize money and become extremely well respected in the mathematics community! Wait a minute, really? How can I use this to become rich? Before we answer that, let’s see what exactly is the difficulty in solving the problem. Shall we?
The Essence of the Problem
P vs NP problem comes in the field of computational complexity. It is so theoretical in nature that it has become less about computer science and more about mathematics. That’s the reason it was included in the Millennium Prize Problems list! Let’s say we have a question but we don’t know the answer to that question. Given a probable solution, we can verify whether or not it’s correct. But arriving at that solution in the first place is not very easy.
Let’s consider a simple example. You are asked to find 10 people on earth whose weights are in increasing order and differ by 2 pounds each. Their weights should form an arithmetic progression with a common difference of 2. There are billions of people on earth. If you pick 10 people randomly, you can quickly verify whether or not they are the right set of people. But finding the right set of people from billions of people is not as easy right? Given the fact that a solution can be quickly verified, P vs NP problem asks if a solution to these problems can also be found quickly. May be we are just not solving it the right way!
What is P and NP?
P stands for polynomial time and NP stands for non-deterministic polynomial time. Now what does that mean? Consider the problem of sorting a bunch of numbers. In computer science, rather than looking at time in terms of minutes and hours, people tend to look at the amount of time as a function of the number of elements the algorithm has to process. If there are N numbers and you are using the simple bubble sort, you will have look at each element twice before deciding where it will be placed. Hence the complexity is N^2. This is called polynomial time (the number ‘N’ occurs in the base). Consider a lock whose password is a binary number. Let’s say there are N digits. If you forget your password, you will have to try 2^N possible combinations to get the right password in the worst case. This is called non-polynomial time (the number ‘N’ occurs in the exponential).
If an algorithm whose execution time is proportional to N takes 1 second to perform a computation involving 100 elements, then an algorithm whose execution time is proportional to N^3 takes almost three hours. But an algorithm whose execution time is proportional to 2^N takes 300 quintillion years. And that discrepancy gets much, much worse the larger N grows. This is totally infeasible based on the current algorithms and the computational power available. Given a password, we can quickly verify if it’s right or wrong. Since we can verify the solution so quickly, why can’t we find the solution quickly as well? This is the question posed by P vs NP and it has enormous implications.
What are those implications?
If P=NP were proved true, there would be many serious real-world consequences. All known encryption schemes rely on the fact that prime factors of large numbers are something that can be feasibly verified but not calculated. It means that if you take two very big prime numbers, multiply them and give the product to the outside world, it will be very difficult for an attacker to get those two initial prime numbers back. If you are given two prime numbers, you can quickly verify if they are the right numbers. It’s just simple multiplication! If P=NP is true, that means there would also be feasible ways to calculate prime factors, and hence people can decrypt codes without their private keys. Hacking into secure systems will become trivial because we now have a feasible way to systematically get the password! So if someone does prove P=NP, all hell will break loose. If you are evil, then you will keep your proof a secret and probably go ahead with your taking-over-the-world plan!
Is P really equal to NP?
Most computer scientists seem to suspect that P does not equal NP. MIT Computer Scientist Scott Aaronson gives a very nice explanation as to why P=NP is not true. He says that if P=NP is true, then the world would be a very 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 Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it? I agree that this is a very philosophical argument, but this is how complex it has gotten over the years. People are turning to philosophical arguments to get to the higher truth!
Why is this problem still unsolved?
People have been working on it for so long but nobody has successfully proved or disproved it yet. In fact, consider the example of finding a proof for the P vs NP problem. This problem belongs to the NP category (NP-Complete to be specific). It is in NP because checking formal proofs can be done efficiently. The hard part is finding them in the first place, or at least we think it’s hard as of now (until we solve P vs NP problem). Do you see the irony and the beauty of this?
In every case, we know of no efficient exact algorithm, and the non-existence of such an algorithm is equivalent to proving P not equal to NP. So are we close to a solution? It seems the best we know is that we don’t know much! Arguably, the most substantial advances in the P vs NP saga are negative. They mostly show we cannot possibly hope to resolve P as different to NP by familiar techniques. In 2007, Alexander Razborov and Steven Rudich were awarded the Gödel Prize (often touted as the Nobel Prize of Computer Science) for their work in showing that no “natural proof” can prove P unequal to NP. It’s still not a complete solution to the problem. Technically, it means that there might be “unnatural” proofs! As long as there is a tiny ray of hope, people will keep working.
————————————————————————————————-
Perpetual Enigma 