P, NP, NP-Complete & NP-Hard

Some problems are solved in polynomial time — sorting, shortest paths, MST. Others, like TSP, 0/1 knapsack and graph colouring, have resisted every attempt for decades. Complexity theory explains this difference.

#Decision problems

Complexity classes are defined for decision problems, whose answer is yes or no. Optimisation problems have decision versions: "Is there a tour of length ≤ k?" instead of "What is the shortest tour?". If you can solve one quickly, you can usually solve the other.

#The class P

P = decision problems that can be solved in polynomial time, O(nᵏ) for some constant k. These are considered tractable.

Examples: sorting, searching, shortest paths, MST, matching, primality testing (AKS, 2002).

#The class NP

NP (nondeterministic polynomial) = decision problems whose yes-answers can be verified in polynomial time, given a suitable certificate (a proposed solution).

Example — SUBSET-SUM: "Do some of these numbers add up to 15?" Finding a subset may be hard, but checking a proposed subset is easy: add it up.

Every problem in P is also in NP (if you can solve it, you can verify it), so P ⊆ NP.

#Reductions

Problem A reduces to problem B (A ≤ₚ B) if any instance of A can be transformed in polynomial time into an instance of B with the same answer. Then B is at least as hard as A: a fast algorithm for B would give a fast algorithm for A.

#NP-complete and NP-hard

• NP-hard: every problem in NP reduces to it. It is at least as hard as anything in NP (it need not be in NP itself, and need not be a decision problem).
• NP-complete (NPC): NP-hard and in NP — the hardest problems inside NP.

Cook–Levin theorem (1971): SAT (Boolean satisfiability) is NP-complete. It was the first. To show a new problem X is NP-complete:

1. Show X ∈ NP (a certificate can be checked in polynomial time).
2. Reduce a known NP-complete problem to X.

#Famous NP-complete problems

#P vs NP

Nobody knows whether P = NP. If any single NP-complete problem had a polynomial algorithm, every NP problem would — so P would equal NP. Most researchers believe P ≠ NP. It is one of the seven Millennium Prize Problems (US $1 million prize).

#Coping with NP-hard problems

1. Exact but exponential: backtracking, branch and bound, DP (fine for small n).
2. Approximation algorithms with guaranteed ratios: e.g. a 2-approximation for vertex cover; for metric TSP, the MST-based tour is at most 2 × optimal.
3. Heuristics: greedy, local search, simulated annealing, genetic algorithms — good answers quickly, no guarantee.
4. Special cases: 2-SAT and 2-colouring are in P; knapsack with small W uses the O(nW) DP.