P versus NP

The statement. P is the set of problems a computer can solve in time polynomial in the input size; NP is the set whose proposed solutions can be checked in polynomial time. Is P = NP?

In plain words. Checking a completed Sudoku is easy; solving one from scratch seems hard. Checking that a number factors as p × q is easy; finding p and q is the hardness cryptography relies on. P = NP would mean every such “easy to check” problem is secretly easy to solve. Almost everyone believes P ≠ NP; nobody can prove it.

What you need first. Stage 9 (logic, truth tables, counting — the satisfiability problem is a truth-table question), Stage 10 (factoring, why it is slow), Stage 1–2 for reading growth rates like n², 2ⁿ.

The parts. (1) What counts as fast: polynomial vs exponential time, and why the distinction survives changing computers. (2) NP-completeness (Cook–Levin, 1971): thousands of problems — satisfiability, travelling salesman, graph colouring — are each as hard as all of NP, so solving any one fast solves them all. (3) Why the obvious approaches fail: diagonalisation and circuit lower bounds each hit a proven barrier. (4) What a proof would need: a genuinely new way to show that no algorithm can exist.

What is known. Exponential lower bounds exist only for restricted models of computation; the three known barriers (relativisation, natural proofs, algebrisation) explain why current techniques cannot work. A Millennium Prize problem.