P vs NP Problem: Implications and Current Progress

What if someone tells you that the entire existing security protocols of the internet can be broken by proving a mathematical equation? A clever person like you will say: It can be or it can’t be but who knows until someone proves the equation? Yes, you are right. You don’t know if the problem can ever be solved. But, if someone solves the problem then you can talk about its impact.

There are many such problems in this world that are hard to solve but once you solve them, it’s easy to verify the solution. The problems which are non-deterministic and the problems which are undecidable. Simply, the problems that we would love to solve but are unable to do so exactly.

In mathematics, there are several complexity classes for the problems. If you can solve a problem in polynomial time (we can predict the maximum amount of time it will take to solve the problem), such a problem will be called the ‘P-class‘ problem. But, if you are not sure about the solution in polynomial time, such a problem will be called ‘NP-class‘ problem. P class is the set of problems that can be solved in polynomial time. NP is the set of problems whose solutions can not be determined but can be verified in polynomial time.

Here, the first two paragraphs are about NP-class problems.

Ok, I know that you are reading this article to know about that magical equation that, once proved, can break all the existing security protocols of the internet. In fact, the Clay Institute is offering one million dollars for a solution to the problem. So let’s talk about the equation which I considered you might be interested in.

Is P=NP?

Yes, two operands and an operator. Is ‘P-class problem‘ equal to ‘NP-class problem‘? Well, this is the major unsolved problem in computer science. Does it ask whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer? According to the definitions we discussed:

1. A yes-or-no problem is in the P class if the answer can be computed in polynomial time.
2. A yes-or-no problem is in NP class if a yes answer can be verified in polynomial time.

Now we can say that if a problem is in the P class, then it is in the NP class also. Because for any problem in P, we can verify the answer by simply recalculating the answer. Now, the question is, whether all problems in NP are in P. Does the fact that we can verify an answer in polynomial time mean that we can compute that answer in polynomial time?

There are a large number of important problems which is known to be NP-complete (basically, if any of these problems are proven to be in P, then all NP problems are proven to be in P). If P = NP, then all of these problems will be proven to have an efficient (polynomial time) solution.

There are many High-IQ people (scientists) who believe that P!=NP but they have no proof to satisfy. So folks, if you don’t have a job yet, try this one, try to prove it.

Here is Best Explanation of P=NP problem by Siraj Raval

What happens when you prove P=NP?

1. You will get 1 million dollars.

P = NP is more than just an abstract mathematical puzzle. It’s a math problem that protects the government, runs the Internet, and makes online shopping possible.

According to Steven de Rooij‘s answer on quora:

No-one is going to prove that because it’s simply not true, but if someone should do it anyway, then it depends very much on the nature of the proof. It could be that the proof establishes that these two classes of problems must be the same, but does not really provide much insight as to how problems in NP can be solved in polynomial time. In that case, a large part of the mystery would remain, but people would start working really hard on understanding how it is possible that all these seemingly extremely hard problems (such as the traveling salesman or the knapsack problem) can possibly be easy after all.

Finally, if the proof really shows how problems in NP can be solved efficiently, then we suddenly have to rethink all our cryptography software and a whole lot of new algorithms will be devised to solve all kinds of problems much faster than before, with implications that are… hard to predict.

Yes, we will have to have to rethink all our cryptography software. One reason cryptographic software could be affected by proving P = NP is by having the potential to have an efficient solution to the Boolean satisfiability problem (3SAT). The result would be all of Public-key cryptography and ciphers such as AES to be broken, which basically nullifies all of modern cryptography. [Source]

There will be a lot of new possibilities and new threats in the world of computer science. If P=NP will be proven, the world that we know today will be a different world.

Vinay Deolalikar, a research scientist at HP Labs in Palo Alto, CA, posted his “proof” online and the early response to his proof was respectful his colleagues immediately began dissecting the proof on academic blogs and wikis and now the current consensus is that Deolalikar’s approach is fundamentally flawed.

That’s all folks, My mission was to create awareness about this problem with the slight clickbait-looking title but that was needed to make you land here. This article was written for everyone who can understand simple English without messing their mind with math. In the end, I would like to say, Don’t be selfish and share this article. Thanks.