The 20 definitions you must write precisely

1. f = O(g): ∃ c, n₀ > 0 : f(n) ≤ c·g(n) ∀ n ≥ n₀ (Ω: ≥; Θ: both).
2. Time/space complexity: worst-case steps / cells used as a function of input size n.
3. Decision problem / language: YES/NO question; L = set of YES instances.
4. P: decidable deterministically in poly time.
5. NP: ∃ poly-time verifier with poly-size certificates (equivalently: NTM poly time).
6. co-NP: complements of NP languages (short NO-certificates).
7. A ≤ₚ B: poly-time f with x ∈ A ⟺ f(x) ∈ B.
8. NP-hard: every NP problem ≤ₚ it. NP-complete: NP-hard ∧ ∈ NP.
9. Turing machine: (Q, Σ, Γ, δ, q₀, q_acc, q_rej); configuration = state+tape+head.
10. NTM: δ maps to a set of moves; accepts iff some branch accepts.
11. Cook–Levin: SAT is NP-complete (tableau + 2×3 windows).
12. 3-SAT: CNF, exactly 3 literals/clause; NP-complete via clause splitting.
13. CLIQUE: k pairwise-adjacent vertices; NP-complete from 3-SAT (literal vertices, k = m).
14. PSPACE: poly space, any time; = NPSPACE (Savitch: NSPACE(f) ⊆ SPACE(f²)).
15. TQBF: truth of fully quantified Boolean formula — PSPACE-complete; quantifiers = game moves.
16. EXP: time 2^poly; P ⊊ EXP (time hierarchy) — unconditional separations exist.
17. ρ-approximation: poly-time, always within factor ρ of OPT (proved!).
18. PTAS / FPTAS: (1+ε)-approx in poly time for each fixed ε / poly in n and 1/ε.
19. Interactive proof / IP: prover-verifier dialogue, randomised verifier, completeness + soundness; IP = PSPACE (Shamir).
20. Pseudo-polynomial / weak vs strong NPC: poly in numeric value (SUBSET-SUM DP) vs hard even with small numbers (TSP).

The relationships table

L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE = IP ⊆ EXP ⊆ NEXP
proved strict:  P ≠ EXP,  NL ≠ PSPACE          everything else: OPEN
P ⊆ NP ∩ co-NP;   NP =? co-NP open;   BQP ⊉ NP (conjectured)

The reduction map to reproduce on demand

every NP problem ──Cook–Levin──▶ SAT ──split──▶ 3-SAT
3-SAT ──▶ CLIQUE ──complement──▶ IND-SET ──V∖S──▶ VERTEX-COVER
3-SAT ──▶ SUBSET-SUM (digit columns)     3-SAT ──▶ 3-COLOURING (palette+OR)
3-SAT ──▶ HAM-CYCLE ──weights 1/2──▶ TSP(decision)

Standard exam questions & answer skeletons

Q: "Prove X is NP-complete." — 4 steps: ① certificate ⟹ X ∈ NP; ② choose source A (say why it fits); ③ construction f + "computable in poly time"; ④ iff both directions, decoding even unintended solutions. Never reduce X → A!

Q: "Show sorting needs Ω(n log n) comparisons." — decision tree, ≥ n! leaves, height ≥ log₂(n!) = Θ(n log n) by Stirling.

Q: "State and sketch Cook–Levin." — SAT ∈ NP (assignment certificate); hardness: t×t tableau of NTM configurations; variables x[i,j,s]; φ_cell ∧ φ_start ∧ φ_move (2×3 legal windows — constant list since machine is fixed) ∧ φ_accept; poly size; satisfiable ⟺ accepting branch exists.

Q: "Explain consequences of P = NP." — crypto collapses (key recovery is NP-search), optimisation & proof-finding automated, learning optimal; caveat: needs small exponents to matter practically.

Q: "2-approximation for vertex cover + proof." — greedy matching, both endpoints; OPT ≥ |M| (must hit each matched edge), ALG = 2|M| ≤ 2·OPT.

Q: "Why doesn't a fast SAT solver in industry contradict NP-completeness?" — NP-completeness is worst-case; industrial instances have structure (clause learning exploits it); hard families still force exponential behaviour.

Last-minute traps

• NP = nondeterministic-polynomial, not "non-polynomial"; P ⊆ NP always.
• NP-hard ≠ NP-complete (hard may lie outside NP: TSP-optimisation, halting).
• Reduction direction: hardness flows from known to new.
• "Polynomial in the value" ≠ "polynomial in the input size" (SUBSET-SUM!).
• Savitch kills the space version of P vs NP — say "PSPACE = NPSPACE" with confidence, and remember the time version is the open one.

The formula & fact sheet (one glance before entering the hall)

Asymptotics:  log n ≺ n^ε ≺ nᵏ ≺ cⁿ ≺ n!          (each strictly slower than the next)
Sorting:      comparison lower bound Θ(n log n);  merge/heap sort achieve it
Searching:    binary search Θ(log n) — optimal among comparison algorithms
Graphs:       BFS/DFS O(n+m); Dijkstra O((n+m) log n); Bellman–Ford O(nm); Floyd–Warshall O(n³)
Simulations:  multi-tape → 1-tape: t → t²;  NTM → DTM: t → 2^O(t);  Savitch: f → f²
Counting:     2^(2^n) Boolean functions on n inputs; almost all need circuits ≈ 2ⁿ/n
Approx:       vertex cover 2;  metric TSP 3/2 (Christofides) or 2 (double-MST);
              set cover ln n;  knapsack FPTAS (1−ε in time poly(n, 1/ε))

Master class table (reproduce from memory — it answers half the short questions)

The 12 must-do questions (write them, don't read them)

1. From the definition, prove 7n³ + 3n = O(n³) and show n³ ≠ O(n²). (Unit 1, 4–5 marks)
2. Define P, NP, NP-hard, NP-complete; draw the containment diagram; one example each. (Unit 1, 6–8)
3. Prove: if any NP-complete problem is in P, then P = NP. (Unit 1, 4)
4. Define ≤ₚ; prove transitivity; explain the direction trap with an example. (Unit 1, 5)
5. Define a TM as a 7-tuple; design and trace one for {0ⁿ1ⁿ}; state its time and space. (Unit 2, 6–8)
6. Define NTM acceptance; prove verifier-NP = NTM-NP (choice string = certificate). (Unit 2, 6)
7. State Savitch's theorem; sketch the midpoint recursion; conclude PSPACE = NPSPACE. (Units 2/4, 5)
8. State Cook–Levin; reproduce the seven-line tableau proof skeleton. (Unit 3, 8–10)
9. Prove 3-SAT NP-complete via clause splitting — both directions of the chain argument. (Unit 3, 6–8)
10. Prove CLIQUE NP-complete from 3-SAT — full gadget, both directions, polynomiality. (Unit 3, 8–10)
11. Prove an unseen problem NP-complete by the 4-step recipe — practise on DOUBLE-SAT and PARTITION until automatic. (Unit 3, 8–10)
12. Vertex-cover 2-approximation with proof, plus short notes on PTAS/FPTAS, IP = PSPACE, and consequences of P = NP. (Unit 4, 5–8 each)

Common mistakes that cost real marks

The night before: a 60-minute pass

1. (15 min) Write the 20 definitions from memory; check against the list at the top of this lesson.
2. (10 min) Draw the class-containment map and the reduction map blind, then compare.
3. (20 min) Write the Cook–Levin skeleton and one full gadget reduction (CLIQUE or PARTITION) on paper.
4. (10 min) Recite the four coping strategies for NP-hardness and the vertex-cover ratio-2 proof.
5. (5 min) Read the mistakes table once. Then sleep — pattern-matching reductions needs a fresh head more than one extra hour of notes.

In the hall: structuring answers under time pressure

• Definitions first, displayed one per line — they are scanned for keywords.
• For reductions, write the recipe's four step names as headers, then fill them in: partial credit attaches to named steps even if the gadget wobbles.
• For "short notes", prefer the topics this course tabulated (complexity classes, approximation spectrum, barriers, weak vs strong NPC) — structured answers read as mastery.
• Two unbreakable rules: never leave the membership-in-NP sentence unwritten, and never reduce in the wrong direction. Those alone are worth several marks per paper.