Prerequisite: NP-Completeness
NP Problem:
The NP problems set of problems whose solutions are hard to find but easy to verify and are solved by Non-Deterministic Machine in polynomial time.
NP-Hard Problem:
A Problem X is NP-Hard if there is an NP-Complete problem Y, such that Y is reducible to X in polynomial time. NP-Hard problems are as hard as NP-Complete problems. NP-Hard Problem need not be in NP class.
If every problem of NP can be polynomial time reduced to it called as NP Hard.
A lot of times takes the particular problem solve and reducing different problems.
example :
- Hamiltonian cycle .
- optimization problem .
- Shortest path
A problem X is NP-Complete if there is an NP problem Y, such that Y is reducible to X in polynomial time. NP-Complete problems are as hard as NP problems. A problem is NP-Complete if it is a part of both NP and NP-Hard Problem. A non-deterministic Turing machine can solve NP-Complete problem in polynomial time.
A problem is np-complete when it is both np and np hard combines together.
this means np complete problems can be verified in polynomial time.
Example:
- Decision problems.
- Regular graphs.
Difference between NP-Hard and NP-Complete:
| NP-hard | NP-Complete |
|---|---|
| NP-Hard problems(say X) can be solved if and only if there is a NP-Complete problem(say Y) that can be reducible into X in polynomial time. | NP-Complete problems can be solved by a non-deterministic Algorithm/Turing Machine in polynomial time. |
| To solve this problem, it do not have to be in NP . | To solve this problem, it must be both NP and NP-hard problems. |
| Time is unknown in NP-Hard. | Time is known as it is fixed in NP-Hard. |
| NP-hard is not a decision problem. | NP-Complete is exclusively a decision problem. |
| Not all NP-hard problems are NP-complete. | All NP-complete problems are NP-hard |
| Do not have to be a Decision problem. | It is exclusively a Decision problem. |
| It is optimization problem used. | It is Decision problem used. |
| Example: Halting problem, Vertex cover problem, etc. | Example: Determine whether a graph has a Hamiltonian cycle, Determine whether a Boolean formula is satisfiable or not, Circuit-satisfiability problem, etc. |
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
