P versus NP Problem
P versus NP is a major unsolved problem in computer science, specifically in computability theory and computational complexity theory. The solution also will have profound implications in the fundamental understanding of mathematics, cryptography, artificial intelligence, life sciences, philosophy, economics and many other fields.
It is one of the seven millenium problems selected by Clay Mathematics Institute.
We humans invented computers because we are not very good at performing complex calculations. Computers have amazing computational power as they were designed to be such, but have no thinking power. One major implication of which is they can not solve a real world problem entirely on their own. They do not possess the ability to transform a given problem into a series of computations.
So we humans need to describe them how to solve a given problem, basically the ‘which and how’ about the computations.
The description has to be ‘unambiguous’ as it has to be followed by something which can not derive any sense out of ambiguity.
This unambiguous description about how to solve a given problem is called an “Algorithm”.
A computational problem always has some input data, and the solution is called the output data. An algorithm takes as input the input data of the problem and produces an output, which is the solution.
In order for an algorithm to reach to the solution, it needs ‘resources’, which can be anything the algorithm needs other than the input data.
For example; time needed to reach to solution, space needed to store intermediate computation data etc. can be called resources.
The input data of the problem can keep changing, for example; ‘how to multiply two numbers’ is a problem, but the numbers themselves can be anything and can change from one instance of the problem to another.
Also the numbers can be of any given size, this measurement of input data is called “input-size”.
Generally, resources required by an algorithm increase with the increase in input-size.
This growth in resource requirement with respect to the growth in input-size is called “asymptotic growth” and is represented as a ‘function of input-size’.
If the asymptotic growth of an algorithm can be represented as a polynomial function, then it’s called a “polynomial-time” algorithm and the problem is called to be solvable in polynomial-time.
Sometimes it’s possible to break a problem in terms of another problem.
For example, the problem of multiplication can be broken into problem of addition.
So if one figures out how to perform addition, then multiplication can be performed by performing repetitive addition.
This conversion of one problem into another is called “reduction”.
If both the time required in conversion and number of repetitions is polynomial, then the reduction is called “polynomial-time reduction”.
Computational Complexity Classes
Asymptotic growth is also known as “complexity”.
According to their complexity, problems in computer science have been classified into various categories.
These classes are called “computational complexity classes”.
For understanding the P vs NP problem, we need to understand four complexity classes: P, NP, NP-Complete and NP-Hard.
P is a set of problems which can be solved in polynomial-time.
NP is a set of problems which may or may not be solved on polynomial-time.
But if one has the solution, the correctness of the solution can be verified in polynomial-time.
Intuitively, all problems in P also belong to NP, as solutions of P can be verified in polynomial-time just by solving them.
NP-Hard is a set of problems to whom any problem in NP can be reduced to in polynomial-time.
There are no known polynomial-time algorithms to solve these problems. Also, some of these may not even be verifiable in polynomial-time, meaning these may or may not belong to NP.
NP-Complete is a set of problems which belong to both NP-Hard and NP.
Meaning, these are NP-Hard problems whose solution can be verified in polynomial-time.
NP-Complete is an intersection of sets NP and NP-Hard.
The classes in increasing order of complexity:
P < NP < NP-C < NP-H
It asks whether every problem whose solution can be verified in polynomial-time (NP) can also be solved in polynomial-time (P).
Meaning whether or not P = NP.
In other words, it asks whether there exists a polynomial-time algorithm for any of the NP-Complete problems.
Although highly unlikely, but if it turns out that P = NP with a ‘constructive and efficient’ proof, then it will be a groundbreaking achievement in mathematical theorem prooving, protein structure prediction which in turn implies considerable advances in life sciences, biotechnology, bioinformatics, structural genomics, genome sequencing, medicine, drug design, may provide treatments for some of the incurable diseases; more efficient compiler design, better circuit design, most efficient transport routing, scheduling, logictics, lot more easier and accurate machine learning, natural language processing, computer vision, image recognition, weather forecasting, accurately predicting earthquakes and other natural phenomena and many more far-reaching consequences, this is just the surface.
As one of the major negative consequences, it will break all cryptosystems based on integer factorisation which implies it will break the entire modern internet security infrastructure.
As a philosophical consequence, it will change the picture of reality, where in solving a problem and verifying the solution would mean the same thing!
This will have a huge deal of implications on how we understand the world and reality.