# 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

Hi Sir,

Your posts are excellent. the content very much useful to students and scholars and faculties.

Thanks you very much sir. Its motivating from you

Is this correct…?

“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.”