Chapter 14+: Reductions and NP-Completeness
Vol 2: Algorithm Forest Adventure · Station 14+ (Optional Deep Dive)
Metadata Card
| Attribute | Value |
|---|---|
| Core Idea | Some problems are inherently hard — don't blame your code |
| Keywords | P vs NP NP-Complete NP-Hard Reduction TSP 3-SAT Vertex Cover Approximation Algorithm |
Your Progress
Deep in the forest, you find problems that no one can solve efficiently. Some look different but are actually the same (reduction), belonging to a mysterious family called NP-Complete.
Breakthrough · Origins
P vs NP Intuition
- P: Problems solvable in polynomial time (sorting, shortest path, DP)
- NP: Problems whose solutions are verifiable in polynomial time (sudoku, 3-SAT)
- NP-Complete: The hardest problems in NP — if you solve one, you solve all
- NP-Hard: At least as hard as NP-Complete (includes undecidable problems)
Reduction: A ≤p B
If you can convert any instance of problem A to problem B in polynomial time, then A is not harder than B.
Classic NP-Hard Problems
- TSP: Visit all cities with shortest path (O(n!) brute force)
- Vertex Cover: Find ≤ k vertices covering all edges
- 0-1 Knapsack: Optimal subset with weight ≤ W
Living with NP-Hard Problems
| Strategy | When | Cost |
|---|---|---|
| Exact search + pruning | n ≤ 30 | Exponential |
| Approximation algorithm | Bounded error okay | Loses optimality |
| Heuristic (GA, SA) | No theoretical guarantee | Unbounded error |
| Parameterized algorithm | Small parameter | Exponential only in parameter |
Verification Checklist
- [ ] Can explain P, NP, NP-Complete, NP-Hard in your own words
- [ ] Understands reduction (problem A → problem B translation)
- [ ] Can recognize NP-Hard problems intuitively
- [ ] Knows practical strategies when facing NP-Hard problems
Traveler's Notes
- NP-Complete's real value: "Don't blame yourself for not solving it — the problem is inherently hard"
- Reduction is a mental model: "What known problem does this look like?"
- Approximation algorithms are 10× more valuable than exact algorithms in production
→ Next Stop Preview
Chapter 14+ (Part 2): Amortized Analysis — "Expensive occasionally, cheap on average."