P vs NP

Takeaway

Is every efficiently checkable problem also efficiently solvable? Most believe P ≠ NP, implying inherent limits on algorithmic efficiency.

The problem (before → after)

Before: Many search problems admit quick verification but no known fast algorithm.
After: NP-completeness shows a vast class of problems are polynomial-time equivalent under reductions; a fast algorithm for one yields fast algorithms for all.

Mental model first

Checking a crossword is easy; creating one that fits all clues is hard. NP asks: if you can quickly check a solution, can you always quickly find one?

Just-in-time concepts

Classes: P, NP, co-NP; nondeterminism as “lucky guesses.”
Reductions: Karp reductions preserve polynomial time.
NP-complete: SAT, 3-SAT, CLIQUE, TSP (decision), etc.

First-pass solution

Cook–Levin shows SAT is NP-complete by encoding computations into formulas. Karp’s reductions propagate hardness to many problems.

Approximation and fixed-parameter tractability offer partial relief.
Oracle separations and relativization barriers; natural proofs barrier.
Proof complexity links to circuit lower bounds.

Principles, not prescriptions

Reductions organize algorithmic knowledge; hardness is transferable.
Seek structure (special cases) or relaxations (approximation) when facing NP-complete problems.

Common pitfalls

Confusing “hard in worst case” with “always hard.”
Assuming NP-complete means unsolvable in practice.

Connections and contrasts

See also: [/blog/halting-problem-undecidability], [/blog/branch-and-bound], [/blog/benders-decomposition].

Quick checks

What does P=NP imply? — Efficient algorithms for SAT and countless others.
Is factoring NP-complete? — Not known; in NP ∩ co-NP (via certificates).
What are barriers to proving P≠NP? — Relativization, natural proofs, algebrization.