Part 4 · 1 chapters · ~8 min

P, NP and Reductions

Polynomial time and why it is the line, P and NP, verification versus search, the Cook-Levin theorem and SAT, Karp's reductions, NP-complete problems engineers meet (scheduling, bin packing, routing, graph colouring, knapsack), NP-hard optimisation, and pseudo-polynomial algorithms.

6

Recognising hard problems

code
// knapsack: NP-hard in general, but pseudo-polynomial: O(n × W) is fine when W (capacity) is small
function bestValue(items: { w: number; v: number }[], W: number) {
  const dp = new Array(W + 1).fill(0);
  for (const { w, v } of items) for (let c = W; c >= w; c--) dp[c] = Math.max(dp[c], dp[c - w] + v);
  return dp[W];
}
// verification is easy: checking a proposed delivery route visits every stop within 8 hours takes O(n);
// finding the shortest such route (TSP) is NP-hard
product featureunderlying problem
delivery or dispatch routingtravelling salesman / vehicle routing: NP-hard
packing orders into vans, VMs onto hostsbin packing: NP-hard
exam, shift or meeting timetablinggraph colouring / constraint satisfaction: NP-hard
choosing promos within a budgetknapsack: NP-hard, pseudo-polynomial DP
dependency resolution with version constraintsSAT: NP-complete (npm, apt, pip resolvers use SAT-like solvers)
P, NP AND NP-COMPLETE
easy to solve, easy to check, and the hardest of the checkable
PSolvable in polynomial time:sorting, shortest paths, matching.NPA proposed answer can be checkedin polynomial time.NP-completeIn NP, and every NP problemreduces to it: SAT, 3-colouring,TSP decision.NP-hardAt least as hard as NP-complete;may not even be in NP.reductionTurn problem A into B cheaply: Beasy ⇒ A easy; A hard ⇒ B hard.P = NP?Open since 1971; most researchersbelieve P ≠ NP.
swipe the figure sideways, or tap expand for full screen
1/4
easy to solve
Problems in P have algorithms whose time grows polynomially: n log n sorting, Dijkstra, bipartite matching.
polynomial algorithmssorting, shortest paths