Theory of computation
Automata, formal languages, Turing machines, computability, complexity and P versus NP.
Approximation with guarantees: when the optimum is NP-hard
Approximation ratios, guaranteed algorithms for vertex cover and the travelling salesman, schemes for knapsack and the limits proved by inapproximability.
The Chomsky hierarchy: four classes of formal languages
The Chomsky hierarchy: type 0, 1, 2 and 3 grammars, their matching automata, examples that separate the classes and what is decidable at each level.
The Church-Turing thesis: lambda calculus, recursion, registers
What the Church-Turing thesis claims, why it is not a theorem, and why lambda calculus, recursive functions and register machines are equivalent.
The class coNP: tautologies, certificates for no, the hierarchy
What the class coNP is, why tautologies are coNP-complete, what we know about NP ∩ coNP and how the polynomial hierarchy generalizes the underlying idea.
The class NP: verifiers, certificates and nondeterminism
What it means for a problem to be in NP: two equivalent definitions with verifiers and nondeterministic machines, examples of certificates, common myths.
The class P: what solving in polynomial time really means
Definition of the class P, why polynomial time is the boundary of tractability, the role of input encoding and why pseudo-polynomial ones fall short.
Context-free grammars: derivations and ambiguity
What context-free grammars are, how to write their rules, how to read derivations and parse trees, and how ambiguity can be removed with precedence levels.
Context-free pumping lemma and closure properties
How to prove a language is not context-free: the pumping lemma with two pumped parts, worked examples and the closure properties worth using as shortcuts.
Deterministic finite automata: how a DFA works
What a deterministic finite automaton is, how it is defined formally, how to build one step by step and which languages it can and cannot recognize.
Minimizing an automaton: Myhill-Nerode and equivalent states
How to reduce a DFA to its minimum number of states: indistinguishable states, partition refinement and the Myhill-Nerode theorem, with worked examples.
The halting problem: why it is undecidable
The diagonalization proof that no algorithm can decide whether a program halts, explained step by step, with its practical consequences for software.
Kleene's theorem: regular expressions equal finite automata
Kleene's theorem proves that regular expressions and finite automata describe the same languages: both constructions explained with step-by-step examples.
Mapping reductions: proving undecidability by comparison
What a mapping reduction is, which way it must go, worked examples on emptiness and machine equivalence, and how it differs from a Turing reduction.
Nondeterministic automata and the subset construction
How a nondeterministic finite automaton (NFA) works, why it recognizes the same languages as a DFA and how to convert it with the subset construction.
NP-completeness and the Cook-Levin theorem: the first problem
What makes a problem NP-complete, how Cook-Levin proves SAT is NP-complete via the computation tableau, and why one starting problem is enough.
P versus NP: the question, the stakes and why it is so hard
What the P versus NP problem really asks, what would change in each scenario, Ladner's intermediate problems and the known barriers to proofs either way.
Polynomial reductions worked out: from 3-SAT to clique and cover
Three NP-completeness reductions step by step: 3-SAT to independent set, then independent set to clique and to vertex cover, with a worked example.
The Post correspondence problem: undecidability with dominoes
The Post correspondence problem explained with domino examples, the idea of the proof through computation histories and its consequences for grammars.
The pumping lemma for regular languages: how to use it
The pumping lemma for regular languages explained through cycles in automata, the proof-by-contradiction pattern, worked examples and the typical mistakes.
Pushdown automata: the memory that makes parentheses possible
How a pushdown automaton works, why it recognizes exactly the context-free languages and why the deterministic version is strictly less powerful.
Rice's theorem: the limits of automatic program analysis
Rice's theorem explained with examples: why every non-trivial property of what a program does is undecidable, and what can still be analysed automatically.
Space complexity: PSPACE, Savitch's theorem and games
How the memory used by an algorithm is measured, Savitch's theorem, the PSPACE-complete problem TQBF, the link with games and logarithmic space classes.
Turing machine: formal definition, configurations, examples
The Turing machine as a mathematical model: tape, head, transition function, configurations, acceptance and a fully worked example, followed step by step.
Turing machine variants: why they are all equivalent
Multitape and nondeterministic machines, enumerators and two-way tapes: how each one is simulated by the basic model and what the simulation costs in time.
The universal Turing machine: programs as data
How a Turing machine is encoded as a string and how a universal machine runs it: the idea of an interpreter, the simulation itself and its consequences.