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.
NP-Complete and NP-Hard Problems
  • 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-CompleteNP-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

Leave a Reply

Your email address will not be published. Required fields are marked *