P vs NP problems
P problems
Polynomial time problems, commonly known as P problems, are the problems whose solution can be found in polynomial time. A simple example of a P problem is linear search, whose time complexity is , where N is the input size.
NP problems
Nondeterministic polynomial-time problems, commonly known as NP problems, are problems whose solutions can be verified in polynomial time. It is not necessary that we also have a polynomial time algorithm to solve an NP problem. A famous example of NP problems is prime factorization. We can verify a factor of an integer in polynomial time. However, we don’t know any polynomial time algorithm to factorize a given integer.
NP-hard problems
An NP-hard problem is a problem to which we can reduce any NP problem in polynomial time. An NP-hard problem is at least as hard as the hardest NP problem.
An NP-hard problem is not necessarily an NP problem. One such example is the halting problem that asks for a given program and its input, will the program halt or run forever? The halting problem is undecidable and not an NP problem, but it is NP-hard.
NP-complete problems
An NP-complete problem is a problem that is both NP and NP-hard simultaneously. The Traveling Salesman Problem (TSP) is an example of an NP-complete problem. In this problem, different cities and their pairwise distances are given, and the aim is to find the shortest path visiting each city only once and returning to the starting city.
The P versus NP problem
The P versus NP problem is the most important problem in computer science. It asks if the set of P problems is equal to the set of NP problems or not.
If someday it is proved that , it would mean that any NP problem can be solved in polynomial time and if it is proved that , it would mean that an NP problem cannot be solved in polynomial time.
While the equation under question is deceptively simple, it is still an open problem to prove or disprove it. It is one of the Millennium Prize Problems by the Clay Mathematics Institute.
