1.1 The statement

P vs NP: Is P = NP? Equivalently: can every problem whose solutions are quickly verifiable also be quickly solved? Equivalently (via Cook–Levin): does SAT have a polynomial-time algorithm?

Posed formally in 1971 (Cook; independently Levin), foreshadowed in a 1956 letter from Gödel to von Neumann ("how many steps does a proof-finding machine need?"). One of the seven Clay Millennium Prize Problems — $1,000,000 for a proof either way. The near-universal conjecture: P ≠ NP, because verifying feels fundamentally easier than finding — checking a completed Sudoku vs solving it, grading a proof vs discovering it. But feelings are not proofs, and after five decades there is none.

1.2 What we do and don't know

Why is it so hard to prove? Known proof techniques are provably inadequate — three formal "barrier" theorems:

• Relativisation (Baker–Gill–Solovay 1975): there are oracles A, B with Pᴬ = NPᴬ and Pᴮ ≠ NPᴮ, so any proof that relativises (survives adding oracles — as diagonalisation does) cannot settle the question.
• Natural proofs (Razborov–Rudich 1994): the known style of circuit lower-bound argument would, if it worked against NP, break the very cryptography we believe in — self-defeating.
• Algebrisation (Aaronson–Wigderson 2008): the algebraic tricks that bypassed relativisation hit their own wall.

A correct resolution requires a genuinely new idea — that is the honest state of the art.

1.3 Consequences of P = NP (a constructive, fast equality)

A world with a practical SAT algorithm would be transformed:

The classic summary (Scott Aaronson): if P = NP usefully, "everyone who can appreciate a symphony would be Mozart" — the gap between recognising excellence and producing it would close. Important caveat for full marks: P = NP via an O(n^1000) algorithm or a wildly non-constructive proof would change philosophy, not practice — "polynomial" is a direction, and the practical earthquake needs small exponents.

1.4 Consequences of P ≠ NP (the expected world)

• NP-complete problems have no general fast exact algorithm — hardness becomes a law of nature to engineer around (Unit 4's approximation lesson).
• Cryptography gains a necessary condition (though it needs more: average-case hardness and one-way functions — P ≠ NP alone doesn't supply those).
• Ladner's theorem activates: an infinite hierarchy of NP-intermediate difficulties exists; factoring and graph isomorphism are the candidate inhabitants (GI was nearly evicted by Babai's 2015 quasi-polynomial algorithm).

1.5 What about quantum computers? (frequent viva question)

Quantum computing does not resolve P vs NP, and is not believed to solve NP-complete problems efficiently. BQP (quantum polynomial time) contains factoring (Shor's algorithm) — which is why factoring is suspected NP-intermediate — but Grover search gives only a quadratic speed-up (2ⁿ → 2^(n/2)) for unstructured search, and the consensus conjecture is NP ⊄ BQP. The P vs NP question is about the classical mathematical structure of computation, and it survives the quantum era intact.

1.6 Stating the problem with full precision (the 2-mark version)

Let P = ⋃ₖ TIME(nᵏ) and let NP be the class of languages with polynomial-time verifiers. P ⊆ NP holds trivially. The P vs NP problem asks whether the inclusion is proper: does there exist L ∈ NP ∖ P?

Equivalent formulations — any one earns the statement marks; (b) is the shortest: (a) is some (equivalently, every) NP-complete problem in P? (b) does SAT ∈ P? (c) can every language whose membership is verifiable in polynomial time also be decided in polynomial time?

1.7 Ladner's theorem — the structure of NP if P ≠ NP

Ladner (1975): if P ≠ NP, then there exists L ∈ NP with L ∉ P and L not NP-complete.

Proof flavour (one sentence suffices in exams): a delayed-diagonalisation construction "blends" an NP-complete problem with a trivial one, switching slowly enough to defeat, in turn, every polynomial-time decider and every reduction from SAT. The resulting picture (assuming P ≠ NP):

P   ⊊   NP-intermediate territory (factoring? graph isomorphism?)   ⊊   NP-complete summit

So NP is not a two-storey building but a skyscraper: Ladner's construction in fact yields infinitely many inequivalent intermediate levels.

1.8 Where the barrier theorems bite (one line each, for short notes)

A winning proof must be simultaneously non-relativising, non-natural and non-algebrising — that triple filter is the modern, precise statement of why the problem is hard to attack, and a high-yield short-note topic.

1.9 Exam answer skeleton — "Discuss P vs NP and the consequences of P = NP" (8 marks)

1. Define P and NP; note P ⊆ NP; state the question (∃? L ∈ NP∖P) and its SAT formulation.
2. Status: open since 1971; a Millennium Prize problem; consensus expects P ≠ NP; what is proved: P ≠ EXP.
3. If P = NP: cryptography collapses (key recovery is an NP search), optimisation and scheduling become exactly solvable, proof discovery and learning become automatable — give 3–4 rows of §1.3's table with a sentence each.
4. Caveat: constructivity and exponent size decide the practical impact.
5. If P ≠ NP: hardness is permanent; the coping toolkit is approximation, heuristics, special cases; Ladner supplies intermediate problems.
6. Close with one barrier sentence ("relativisation and natural proofs explain the fifty-year stalemate").

Self-check

1. Write the three equivalent formulations of P vs NP.
2. What is the only strict separation proved along P ⊆ NP ⊆ PSPACE ⊆ EXP, and which theorem provides it?
3. Why would a non-constructive or n¹⁰⁰⁰-time proof of P = NP change philosophy more than practice?
4. State Ladner's theorem and name its two candidate witnesses.
5. Grover's algorithm searches 2ⁿ possibilities in about 2^(n/2) steps. Why does that not place NP-complete problems in quantum polynomial time?