NP-hard and NP-complete problems

Background

• P: decision problems solvable in polynomial time by a deterministic TM.
• NP: decision problems whose "yes" answers can be verified in polynomial time (equivalently, solved in polynomial time by a non-deterministic TM).
• A problem A is polynomial-time reducible to B (A ≤p B) if there is a polynomial-time computable f with w ∈ A ⇔ f(w) ∈ B.

NP-hard

A problem B is NP-hard if every problem in NP reduces to B in polynomial time. So B is at least as hard as every problem in NP. An NP-hard problem need not be in NP, and need not be a decision problem.

Examples: the halting problem (undecidable, so not in NP), the optimisation version of the travelling salesman problem.

NP-complete

A problem B is NP-complete if

1. B ∈ NP, and
2. B is NP-hard.

So NPC = NP ∩ NP-hard. These are the hardest problems in NP.

   Assuming P ≠ NP:
   ┌───────────── NP ──────────────┐
   │                               │
   │  ┌─────┐          ┌───────────┼─────────────┐
   │  │  P  │          │    NP-    │             │
   │  └─────┘          │  complete │   NP-hard   │
   │                   │           │  (not in NP)│
   └───────────────────┼───────────┘             │
                       └─────────────────────────┘
   NP-complete = the overlap of NP and NP-hard

Cook–Levin theorem: SAT (satisfiability of Boolean formulas) is NP-complete. Other problems are shown NP-complete by reducing a known NP-complete problem to them (SAT ≤p 3-SAT ≤p CLIQUE, Vertex Cover, Hamiltonian cycle, Subset Sum, and so on).

Why it matters

If any one NP-complete problem has a polynomial-time algorithm, then every problem in NP does, so P = NP. Since no one has found such an algorithm, NP-completeness is taken as strong evidence that a problem is intractable, and approximation or heuristic methods are used instead.