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