P vs NP
The most important open question in computer science — a million-dollar problem you can explain to anyone in one line.
The Question
P = problems we can solve quickly (polynomial time). NP = problems whose answers we can check quickly. The question: if a solution is easy to verify, is it also easy to find? That is, does P = NP?
The intuition it captures: a sudoku is trivial to check once filled in, but hard to solve from blank. Recognizing a great symphony vs composing one. Nearly everyone believes P ≠ NP (finding is genuinely harder than checking) — but after 50 years, nobody has proved it either way.
NP-Completeness
Some NP problems are NP-complete: the hardest in NP, and all equivalent — a polynomial-time algorithm for one would solve every NP problem, proving P = NP. SAT (is this boolean formula satisfiable?) was the first, via the Cook-Levin theorem. Thousands followed:
| NP-complete problem | The question |
|---|---|
| SAT | Can this boolean formula be made true? |
| Travelling Salesman (decision) | Route visiting all cities under length k? |
| Graph coloring | Color the graph with k colors, no clash? |
| Knapsack | Fit value ≥ V into the weight limit? |
| Subset sum | Does some subset add up to exactly T? |
They look unrelated but are secretly the same problem in disguise — each reducible to the others in polynomial time. Crack one efficiently and the whole edifice falls.
Reductions — the Core Tool
You prove a new problem is NP-complete by reduction: show a known NP-complete problem can be transformed into yours in polynomial time. If yours were easy, so would the known-hard one be — contradiction. Reduction is how hardness spreads, and it’s a practical skill: recognizing that your scheduling problem is really graph coloring tells you to stop hunting for a fast exact algorithm.
What Engineers Actually Do About It
“It’s NP-complete” is not the end — it means stop seeking a fast exact, general solution and pick a strategy:
- Approximation algorithms (provably near-optimal)
- Heuristics (greedy, simulated annealing, genetic)
- Exploit structure — real inputs aren’t worst-case
- SAT/ILP solvers — brutally optimized, fast in practice
- Hunt for a polynomial exact algorithm (you won’t find one)
- Assume small inputs stay small
- Ignore that your problem IS one of these in disguise
Interview Questions
Explain P vs NP to a non-expert.
P = problems you can solve quickly. NP = problems where you can check a proposed answer quickly. The question: if an answer is easy to verify, is it also easy to find? Like: checking a filled sudoku is easy, solving a blank one seems hard. Nobody has proved whether they’re actually the same.
What is NP-completeness and why does it matter?
NP-complete problems are the hardest in NP and all inter-reducible: a polynomial algorithm for any one solves all of NP (proving P=NP). So proving your problem NP-complete means a fast exact general solution almost certainly doesn’t exist — redirect to approximation/heuristics.
How do you prove a problem is NP-complete?
Show it’s in NP (solutions checkable in poly time), then reduce a known NP-complete problem (SAT, 3-SAT) to it in polynomial time. The reduction proves that solving yours efficiently would solve the known-hard one.
If a problem is NP-complete, what do you do in practice?
Don’t seek a fast exact general algorithm. Use approximation algorithms with quality bounds, heuristics (greedy, annealing), exploit that real inputs have structure, or throw a mature SAT/ILP solver at it — they handle huge real instances despite worst-case hardness.