P vs NP Problem Explained | Is P Equal to NP?
The P vs NP problem has paramount importance in the field of computer science and mathematics,it asks the very important question of whether a problem that is easily verifiable is easily solvable as well. Hence there comes the necessity to either prove or disprove if P equals NP.
It is in fact such an important problem that it is one of the Millennium prize problem as determined by the Clay Institute of Mathematics and providing a solution to this problem could have you taking back home US $1 million.
If you have eyes on the prize then I suggest we get started understanding what exactly this problem entails.
What exactly is P and NP?
“P” technically stands for Deterministic Polynomial time and “NP” stands for Non-Deterministic Polynomial time. They refer to the time taken by an algorithm to completely run.To understand this better let us take a look at some problems in class P.
P class problems can be solved in polynomial time as well as be verified in polynomial time,an example of such algorithms are the common sorting algorithms. Where in we can easily sort the unsorted list in polynomial time and also verify if the sorted list is correct in polynomial time.
NP class problems refer to those problems that cannot be solved in polynomial but can be verified in polynomial time. An example of this would be a su-do-ku puzzle,it is easy for a computer to check if a given su-do-ku grid is correct but it is extremely hard for a computer to find the solution to one.
In more technical terms a P class problem has a time complexity that increases in a polynomial fashion whereas problems that lie in class NP have a time complexity that increases exponentially.
Are There Only P and NP Type Problems?
The answer is no. P and NP are too narrow sets to hold within them all the types of problems,giving way for more niches to make a place in the entire set.
In order to understand the other subsets of this problem we must take a look at a property called Reduction. Reduction implies that if there is a problem in NP that can be reduced into another form in deterministic polynomial time and that form of the problem is solvable in polynomial time then the original problem in itself is said to be solvable in polynomial time. This creates a new set of problems in relation to P and NP and is called NP-Hard. All optimization problems come under NP-Hard.
Now there is also the case of NP-Complete problems that diagrammatically represent the intersection of the NP set and the NP-Hard set. Here the problem is reduced in polynomial time into another form that then again falls under NP. Decision problems fall in this set of NP-complete. From the diagram it is clear to say that every problem in NP-Complete is NP-Hard but not vice-versa.
Why P and NP matter?
One of the reasons this is of utmost importance is because modern encryption techniques rely on that fact that P does not equal NP. if P were to equal NP then problems such a prime factorization can be solved by computers in polynomial time which literally would give away the keys to our data as prime factorization being hard is an essential property in generating secure keys to transfer and store data . It would also help us understand genome construction aiding advancements in the medical field .
If P is not equal to NP then it would prove that some problems are truly unsolvable guiding science in the right direction. As of now we do not know if P equals or does not equal NP but it surely will shatter many fields of study if either one of the solutions is proven.
comment down below what you think about the P vs N problem. Does P=NP?