Skip to content

Part II – Theoretical Computer Science

The mathematics underneath computing: Hilbert’s decision problem, and Gödel, Church and Turing on what can be computed at all, then complexity theory’s question of what can be computed fast, from Cook and Levin’s NP-completeness to P vs. NP. The algorithmics section tells how sorting, hashing, graph search, the FFT and the simplex method were found, and by whom.

Computability & Logic

  • David Hilbert and the Entscheidungsproblem — the mathematical challenge that created theoretical computer science
  • Gödel and the Incompleteness Theorems — the 1931 proof that mathematics is incomplete; self-reference, Gödel numbering, and the limits that foreshadowed uncomputability
  • Alonzo Church and Lambda Calculus — lambda calculus, Church-Turing thesis, undecidability
  • Automata Theory and Computability — finite automata, pushdown automata, Turing machines: the ladder of computational power and its undecidable ceiling
  • Emil Post — truth tables in 1920, incompleteness in 1921 left unpublished, Formulation 1, production systems, degrees of unsolvability and the correspondence problem
  • Stephen Kleene — Church’s student, general recursive functions, the 1951 RAND memo on nerve nets that introduced regular expressions and the Kleene star
  • The Algorithm as a Concept — from Euclid and Al-Khwarizmi through Turing to algorithmic governance
  • The Busy Beaver Problem — uncomputability as a countable sequence, BB(5) = 47,176,870 proved by an online collaboration in 2024, and BB(6) tangled with number theory
  • Kolmogorov Complexity — information as the shortest program, discovered three times, the sharpest definition of randomness, and a fresh proof of Gödel
  • Solomonoff Induction and AIXI — the 1960 universal prior that learns every computable pattern and cannot be computed, Hutter’s optimal agent, the Hutter Prize, and why a language model compresses images better than PNG
  • Avi Wigderson — zero-knowledge proofs for all of NP, hardness traded for randomness (P = BPP under a believed assumption), the zig-zag product, and the only Abel Prize plus Turing Award
  • Andrey Kolmogorov — the 1933 axioms of probability, the entropy of a dynamical system, and, at 62, the shortest-program definition of information that made randomness a property of the object
  • Gregory Chaitin — program-size complexity at eighteen, the halting probability Ω whose digits no theory can supply, incompleteness measured in bits, and the graph-colouring register allocator
  • Computer-Assisted Proof — the four-color theorem no human could read, Kepler’s “99% certain” referees, and how Coq and Lean turned the machine from suspect to guarantor

Complexity

  • P vs. NP and Complexity Theory — Cook’s theorem, NP-completeness, and the unsolved Millennium Prize Problem
  • Hartmanis and Stearns: Measuring the Cost of Computation — the 1965 paper that named computational complexity and proved that more time buys strictly more computing power
  • Cook and Levin: NP-Completeness on Two Sides of the Iron Curtain — the same theorem discovered independently in Toronto and Moscow, one published at once, one blocked for years
  • Richard Karp and the 21 Problems — the 1972 list that turned Cook’s theorem into a map of hardness, and the Turing Award for it
  • Leslie Valiant and PAC Learning — #P and the permanent, “A Theory of the Learnable” (1984), bulk synchronous parallelism, evolvability, Turing Award 2010
  • Manuel Blum: From Complexity to CAPTCHA — the Blum axioms, coin flipping by telephone, three Turing-laureate students, and the reverse Turing test
  • SAT Solvers — the first NP-complete problem, now solved industrially at a million variables; DPLL, conflict-driven clause learning, Chaff, and chip verification
  • Algorithmic Game Theory — Nash equilibria, Vickrey’s honest auction funding the web through Google’s ad exchange, price of anarchy, and Roth’s kidney chains
  • Spectrum Auctions — Coase asked if he was joking, New Zealand’s NZ$6 license, the 1994 FCC auction design that won a Nobel, bidding in code, the 3G auctions of 2000, and a SAT solver that repacked American television
  • Peter Shor — the 1994 factoring algorithm that broke RSA in principle, and the 1995 code that showed quantum error correction was possible after all

Algorithmics

  • The History of Sorting — from Hollerith’s card sorters through von Neumann’s first program and Hoare’s quicksort to the Timsort bug that shipped for thirteen years
  • Graph Algorithms — Königsberg’s bridges, a Moravian power grid, a classified Cold War rail study, Edmonds’s “good algorithms”, and PageRank
  • Jack Edmonds and the Good Algorithm — the blossom algorithm, and the 1965 digression that first drew the line between polynomial and exponential
  • Hopcroft and Tarjan: Depth-First Search and the Linear-Time Graph — the 1970 sabbatical that made components and planarity linear, the inverse Ackermann bound, splay trees and Fibonacci heaps, the 1986 Turing Award
  • String Matching — the naive loop, Knuth-Morris-Pratt derived from pushdown-automata theory, Boyer-Moore reading backwards, suffix trees, and why genomes are the killer app
  • Hashing — a 1953 IBM memo, the analysis that made it respectable, Bloom filters, consistent hashing, and the day HashDoS turned hash tables into a weapon
  • Hans Peter Luhn — the IBM engineer who described hashing in a 1953 memo, filed the credit-card checksum, had a computer write the first abstract, and invented the KWIC index, all before 1961
  • The Traveling Salesman Problem — an 1832 salesman’s handbook, 49 cities solved by hand at RAND in 1954, the Car 54 contest, Concorde’s 85,900-point record, and the neural networks that could not do it
  • Approximation Algorithms — Graham’s 1966 scheduling bound, Johnson’s greedy set cover, Christofides’s 1.5 that stood for 44 years, Goemans-Williamson’s 0.878, the PCP theorem and the Unique Games Conjecture
  • Network Science and the Small World — Karinthy’s 1929 story, Milgram’s folders, Watts-Strogatz shortcuts, Barabási’s hubs, Facebook’s 3.57 degrees, and why scale-free networks turned out to be rare
  • Randomness in Algorithms — Monte Carlo vs. Las Vegas, the randomized primality test that made RSA real, randomized quicksort, and whether the coins are ever truly necessary
  • Cooley, Tukey, and the Fast Fourier Transform — invented to catch Soviet nuclear tests; anticipated by Gauss in 1805, unpublished
  • Richard Bellman and Dynamic Programming — the Bellman equation from RAND logistics to reinforcement learning, and a naming legend that can’t be strictly true
  • George Dantzig and the Simplex Method — linear programming, the homework legend behind Good Will Hunting, and the optimization of everything
  • Rudolf Kálmán and the Kalman Filter — the noisy-sensor recursion that navigated Apollo and runs in every phone and GPS receiver
  • Monte Carlo Methods — Ulam’s solitaire epiphany, von Neumann’s ENIAC neutrons, and accuracy bought with randomness
  • A* and Shakey the Robot — the “first electronic person” and the pathfinding algorithm in every game and sat-nav
  • Donald Knuth and the Art of Programming — TAOCP, Big-O notation, TeX, and the algorithmics bible