# 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.