What is the difference between P and NP-hard problems?
Overview
The various problems in computer science can be divided into two major kinds:
- P problems
- NP problems
P problems are those that can be solved in polynomial time. NP problems can be both NP-complete and NP-hard.
P problems
These are easier problems to solve. In scientific terms, the problems that can be solved in a polynomial time are called P problems. The polynomial here means that the time complexity can be any polynomial function instead of an exponential one.
There are several common problems in computer science that have been solved and tested in polynomial time.
Examples of polynomial time include:
etc.
NP problems
NP problems do not have a deterministic solution such that they can be solved in polynomial time. Hence, it is known as a non-deterministic polynomial problem.
A polynomial solution to such a problem can only be achieved using a non-deterministic Turing machine. NP problems are a superset of P problems.
NP-hard problems
One kind of NP problem is the NP-hard problem. NP-hard problems are equally hard or harder than NP problems. This implies that they can be more complex and don't need to be a part of the set of NP problems at all.
The problems in computer science can be termed as NP-hard if there is an NP-complete problem that can be reduced to that problem in any polynomial time.
NP-complete problems are ones that are both NP and NP-Hard. In a Venn diagram, it is the intersection of both NP and NP-hard problems.
Conclusion
P | NP |
Are solved deterministically in polynomial time | Can only be solved non-deterministically for a polynomial solution |
Use a deterministic Turing machine | They can only be solved deterministically in exponential time |
Includes string matching, palindrome, Dijkstra, Bellman Ford, and so on | Includes halting, decision subset sum, and so on |