2.1 Class P — solvable fast

P = the class of decision problems (languages) decidable by a deterministic algorithm in polynomial time, i.e. time O(nᵏ) for some constant k.

Members: searching, sorting-based decisions, shortest path (Dijkstra/Bellman–Ford), minimum spanning tree, maximum matching, linear programming, 2-SAT, 2-colourability, and — since the 2002 AKS algorithm — primality testing.

P is robust: it is unchanged whether you compute on a Turing machine, a RAM, or in any reasonable programming language (they simulate each other with polynomial overhead), and it is closed under composition — a polynomial algorithm calling polynomial subroutines stays polynomial.

2.2 Class NP — verifiable fast

Two equivalent definitions (be able to state both!):

Verifier definition. L ∈ NP iff there is a polynomial-time verifier V and polynomial p such that: x ∈ L ⟺ ∃ certificate c, |c| ≤ p(|x|), with V(x, c) = ACCEPT.

Machine definition. NP = problems decidable by a non-deterministic Turing machine in polynomial time (Unit 2 makes this precise).

NP = Nondeterministic Polynomial — not "non-polynomial"! Every problem in P is in NP (P ⊆ NP).

The intuition: NP problems may be hard to solve, but a claimed solution is easy to check:

(co-NP, for contrast, has short certificates for NO answers — e.g. "this formula is unsatisfiable" has no obvious short proof; whether NP = co-NP is also open.)

2.3 NP-hard and NP-complete

Using polynomial-time reductions ≤ₚ (next lesson) we define the "hardest" problems:

NP-hard: L is NP-hard if every problem in NP reduces to L (A ≤ₚ L for all A ∈ NP). L itself need not be in NP. NP-complete: L is NP-complete if (1) L ∈ NP and (2) L is NP-hard.

NP-complete problems are the summit of NP: solve one of them in polynomial time and all of NP collapses into P.

2.4 The four classes side by side

Common trap clarified:

• NP-hard but (probably) not in NP: the optimisation version of TSP ("find the shortest tour" — not a decision problem), and the halting problem (undecidable, hence certainly not in NP, yet NP-hard).
• "NP-complete" is a precise term; "NP-hard" is the one to use for "at least as hard as NP" when membership in NP is unclear.

2.5 Why thousands of problems turned out NP-complete

After Cook (1971) proved SAT NP-complete, Karp (1972) reduced SAT to 21 famous problems — covering scheduling, packing, routing, graph colouring. Today the catalogue runs to thousands across biology (protein folding), economics (market equilibria), games (Sudoku, Minesweeper generalisations) and operations research. One theorem, an entire scientific landscape: that is why the Cook–Levin theorem (Unit 3) is the keystone of the course.

2.6 Three small proofs you must be able to write

Claim 1: P ⊆ NP. Let L ∈ P via algorithm A. Define the verifier V(x, c) = A(x) — it simply ignores the certificate. V runs in polynomial time, and x ∈ L ⟺ V accepts (with, say, the empty certificate). Hence L ∈ NP. ∎ (One paragraph, full marks; ignoring the certificate is the entire trick.)

Claim 2: NP ⊆ EXP. Let L ∈ NP with verifier V and certificate length bound p(n). On input x, enumerate all 2^p(|x|) candidate certificates and run V on each; accept iff some run accepts. Time 2^p(n) · poly(n) = 2^poly(n). ∎ So NP sits between P and EXP — and since P ≠ EXP is proved (time hierarchy theorem), at least one of P ≠ NP, NP ≠ EXP must hold. Embarrassingly, we do not know which.

Claim 3 (the lever of the whole theory). If any single NP-complete problem B is in P, then P = NP. Proof: take any L ∈ NP. Since B is NP-hard, L ≤ₚ B via some polynomial f. Decide L by computing f(x) and running B's polynomial algorithm on it: a polynomial composed with a polynomial is polynomial. ∎ Contrapositive: if P ≠ NP, no NP-complete problem has a polynomial algorithm.

2.7 A worked verifier argument (the reusable template)

Show COMPOSITE = { ⟨n⟩ : n is composite } ∈ NP.

• Certificate: a non-trivial factor d with 1 < d < n.
• Size bound: |d| ≤ |n| in bits — polynomial. ✓
• Verifier: check 1 < d < n and that d divides n (one long division — polynomial in the bit-length). ✓
• Iff: n is composite ⟺ such a d exists ⟺ some certificate makes the verifier accept. ∎

Use exactly this four-line shape (certificate, size bound, polynomial check, iff) for every "show X ∈ NP" question — it is the first half of every NP-completeness proof in Unit 3.

2.8 Ladner's theorem — between P and the summit

Ladner (1975): if P ≠ NP, there exist NP-intermediate problems — in NP, not in P, and not NP-complete.

So (assuming P ≠ NP) NP is not just "easy + complete": an infinite ladder of intermediate difficulties exists. The natural candidate inhabitants are integer factoring and graph isomorphism — both in NP, neither known to be in P, and both believed not NP-complete (e.g. if factoring's decision version were NP-complete, NP = co-NP would follow, which is not believed).

2.9 Frequently confused pairs (exam-trap table)

Exam pointer

The five-mark classic "Define P, NP, NP-hard, NP-complete with examples and a diagram" is answered by: the four boxed definitions (§2.1–2.3), one example each, the containment diagram of §2.3, plus the sentence "if any NP-complete problem is in P then P = NP" (Claim 3). If asked to compare the classes, reproduce §2.4's table.

Self-check

1. State the verifier definition of NP naming all three quantified objects (verifier, polynomial bound, certificate).
2. Why is the halting problem NP-hard but not NP-complete?
3. Prove P ⊆ NP in three lines.
4. If SAT ∈ P were proved tomorrow, what exactly happens to CLIQUE? Trace it through the definitions.
5. Name two suspected NP-intermediate problems and explain why one of them matters to cryptography.