# NP-Complete and NP-Hard Problems

NP-Complete and NP-Hard Problems are interesting classes of problems. These problems are addressed in different ways by computer scientists.

## NP-Complete Problems

- Polynomial time reduction implies that one problem is at least as hard as another problem, within the polynomial time factor. If A ≤
_{p }B, implies A is not harder than B by some polynomial factor. - Decision problem A is called NP-complete if it has the following two properties :
- It belongs to class NP.

- Every other problem B in NP can be transformed to A in polynomial time, i.e. For every B ∈ NP, B ≤
_{p }A.

- These two facts prove that NP-complete problems are the harder problems in class NP. They are often referred to as NPC.
- If any NP-complete problem belongs to class P, then

P = NP. However, a solution to any NP-complete problem can be verified in polynomial time, but cannot be obtained in polynomial time. - Theorem
- Let A be an NP-complete problem. For some decision problem B ∈ NP, if B ≤
_{p }A then B is also an NP-complete problem. - NP-complete problems are often solved using randomization algorithms, heuristic approaches or approximation algorithms.
- Some of the well-known NP-complete problems are listed here :
- Boolean satisfiability problem.

- Knapsack problem.

- Hamiltonian path problem.

- Travelling salesman problem.

- Subset sum problem.

- Vertex covers the problem.

- Graph colouring problem.
- Clique problem.

## NP-Hard Problem

- Formally, a decision problem p is called NP-hard, if every problem in NP can be reduced to p in polynomial time.
- NP-hard is a superset of all problems. NPC is in NP-hard, but the converse may not be true.
- NP-hard problems are at least as hard as the hardest problems in NP.
- If we can solve any NP-hard problem in polynomial time, we would be able to solve all the problems in NP in polynomial time.
- NP-hard problems do not have to be in NP. Even they may not be a decision problem.
- The subset subproblem, the travelling salesman problem is NPC and also belongs to NP-hard. There are certain problems which belong to NP-hard but they are not NP-complete.
- A well-known example of the NP-hard problem is the Halting problem.
- The halting problem is stated as, “Given an algorithm and set of inputs, will it run forever ?” The answer to this question is Yes or No, so this is a decision problem.
- There does not exist any known algorithm which can decide the answer for any given input in polynomial time. So halting problem is an NP-hard problem.
- Different mathematicians have given different relationships considering the possibilities of P = NP and P ≠ NP.
- The relationship between P, NP, NP-Complete and NP-hard is described in below Fig. 8.10.1 assuming that P ≠ NP. This is a widely accepted relationship among these complexity classes.

- Subset sum problem and travelling salesman problem are NPC and also belong to NP-hard. There are certain problems which belong to NP-hard but they are not NP-complete. A well-known example of an NP-hard problem is the Halting problem.
- The halting problem is stated as, “Given the algorithm and set of inputs, will it run forever ?” The answer to this question is Yes or No, so this is a decision problem.
- There does not exist any known algorithm which can decide the answer for any given input in polynomial time. So halting problem is an NP-hard problem.
- Also, the Boolean satisfiability problem, which is in NPC, can be reduced to an instance of the halting problem in polynomial time by transforming it to the description of a Turing machine that tries all truth value assignments. The Turing machine halts when it finds such an assignment, otherwise, it goes into an infinite loop.

## NP-Hard vs. NP-Complete

# | NP-Complete | NP-Hard |

1. | NP-complete problems are decision problems. | The NP-hard problem might not be a decision problem. |

2. | NP-complete problems are harder problems. | NP-hard problems are the hardest problem. |

3. | The NP-complete problems are in NP. | NP-hard problems may not be in NP. |

4. | Problem X is NP-complete if NP problem Y is reducible to X in polynomial time. | Problem X is NP-hard if NP-complete problem Y is reducible to X in polynomial time. |

5. | Ex. 3 SAT problem. | Ex. Halting problem. |

Youtube Channel: CodeCrucks