Introduction to Theoretical Computer Science PDF Download – Boaz Barak (Harvard) BSCS

BSCS students taking a Theory of Computation course — or anyone who wants a rigorous, modern introduction to what computers can and cannot do — can read the complete textbook “Introduction to Theoretical Computer Science” by Boaz Barak, free from its official source at introtcs.org. It’s a 22-chapter, university-level text built directly from Barak’s own Harvard CS 121 course, covering Boolean circuits, Turing machines, uncomputability, Gödel’s Incompleteness Theorem, NP-completeness, randomized algorithms, cryptography, and quantum computing.

This actively maintained work-in-progress edition (most recently compiled December 2023) is published directly by the author and licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International, covering finite computation and Boolean circuits (Part I, Chapters 0–5), Turing machines and uncomputability (Part II, Chapters 6–11), efficient computation and NP-completeness (Part III, Chapters 12–16), and randomization, cryptography and quantum computing (Part IV, Chapters 18–22) — making it both a complete course textbook and a lasting reference for the theory underlying algorithms, security, and the limits of computation itself.

Book Overview

Chapter List

Part I: Foundations

Chapter 0: Introduction

Difficulty: Easy · Theory of Computation · Foundations · Key topics: algorithms vs implementations, place-value systems, grade-school vs naive multiplication, Big-O intuition, specification vs implementation

The opening chapter uses the Babylonian place-value number system versus Roman numerals to show why representation matters, then compares naive repeated-addition multiplication to the grade-school digit-by-digit algorithm, showing the grade-school method needs only about 800 single-digit operations versus roughly 10^19 for repeated addition on 20-digit numbers. It argues that an algorithm’s efficiency is a technology-independent property of the algorithm itself, not of the device running it, and that theoretical computer science studies exactly these inherent properties. It closes by splitting a full algorithm description into three parts: specification (what task), implementation (how), and analysis (how many resources).

Key Points:

• An algorithm’s efficiency is a property of the algorithm itself, independent of whether it runs on silicon or on paper.
• Grade-school multiplication of two 20-digit numbers takes about 800 single-digit operations; naive repeated addition takes roughly 10^19.
• A full description of an algorithm has three parts: specification (what), implementation (how), and analysis (how many resources).
• Place-value number systems (decimal, binary) make large quantities expressible in few symbols; Roman numerals do not.
• Theoretical computer science studies the inherent, technology-independent properties of computation.

Memory Tip: Whenever you meet a new algorithm, ask the book’s own three questions in order: what does it compute (specification), how does it compute it (implementation), and how many steps does that take (analysis).

Common Mistake: Judging an algorithm’s quality only by watching it run once on a small example — the multiplication comparison shows the real gap between algorithms shows up only at scale; the naive method looks fine on 2-digit numbers and catastrophic on 20-digit ones.

Important Questions:

• Why is grade-school multiplication so much faster than repeated addition for large numbers? Repeated addition needs about y additions to compute x times y, which grows with the value of y (exponentially in the number of digits), while grade-school multiplication needs about n^2 single-digit operations for n-digit numbers, so the gap between the two grows explosively as numbers get longer, going from a fraction of a second to more than three millennia of computer time for 20-digit inputs.
• What are the three components of a full algorithm description? Specification (what task the algorithm performs), implementation (the exact sequence of instructions used to perform it), and analysis (how many resources, such as time, the implementation actually uses) — two algorithms can share a specification while differing completely in implementation and analysis.

Chapter 1: Mathematical Background

Difficulty: Easy · Theory of Computation · Foundations · Key topics: sets, functions, logic, quantifiers, Big-O notation, induction, graphs, reading proofs

Reviews the mathematical toolkit the rest of the book assumes: sets and set operations, Cartesian products and the Kleene star, functions and their properties (one-to-one, onto, partial), logical connectives and quantifiers, basic combinatorics, graphs, and a rigorous treatment of Big-O notation. It frames mathematics as the only language precise enough to state questions like whether there is an efficient factoring algorithm and to prove that none exists, since nonexistence claims cannot be settled by experiment. It works through how to read a formal definition carefully, annotating each symbol, using the definition of a one-to-one function as a worked example. Discrete probability is flagged as a topic deferred to a later chapter rather than covered here.

Key Points:

• Mathematics gives a precise, unambiguous definition of concepts like “algorithm” and “efficient” so their existence or nonexistence can be proven, not just observed.
• A function f is one-to-one (injective) if distinct inputs always map to distinct outputs.
• Notation covered: set membership/containment, union/intersection/set difference, Cartesian product A × B, and the Kleene star A* (all finite tuples over A).
• Reading a formal definition means annotating every identifier — is it a set, a function, an element, a number?
• The chapter reviews Big-O, Omega, o, omega and Theta notation for asymptotic growth, used throughout the rest of the book.
• Discrete probability is deliberately deferred to a later chapter, since it is only needed starting in the second half of the book.

Memory Tip: When a proof or definition looks dense, slow down and label every symbol by its type (set, function, element, number) before reading further — the book’s own advice for parsing dense mathematical text.

Common Mistake: Skimming this chapter as filler — nearly every later chapter reuses this exact vocabulary (especially “one-to-one,” “onto,” and Big-O) without redefining it, so gaps here compound quickly.

Important Questions:

• Why does the book insist on precise mathematical definitions of “algorithm” and “efficient”? Some of the book’s central results are nonexistence claims (that no algorithm can solve a certain problem), and there is no experiment that can prove a negative like this; only a mathematical proof, built on precise definitions, can establish that something cannot be done, no matter how much computing power is thrown at it.
• What is the difference between a function being one-to-one and being onto? A function is one-to-one (injective) if no two distinct inputs ever produce the same output; it is onto (surjective) if every element of the codomain is actually produced by some input; a function that is both is called a bijection, the standard way to prove two sets have the same size.

Chapter 2: Computation and Representation

Difficulty: Easy · Theory of Computation · Foundations · Key topics: specification vs implementation, binary representation, prefix-free encoding, Cantor’s theorem, representing numbers and graphs

Establishes that any object — numbers, text, images, graphs, even other programs — can be represented as a binary string, and works through concrete representation schemes for natural numbers, lists, and graphs. It introduces prefix-free encoding as the tool for composing representations of simple objects into representations of complex ones without ambiguity about where one component ends and the next begins. The chapter separates the “what” of a computational task (its specification as a function) from the “how” (an algorithm that computes it), a distinction the book returns to constantly. It closes with Cantor’s Theorem, proving the real numbers cannot be represented exactly as finite binary strings.

Key Points:

• Every computational input or output — numbers, text, graphs, images, programs — is represented as a binary string; nothing is special about 0 and 1 beyond convenience.
• A representation scheme is a one-to-one function E mapping objects to binary strings; one-to-one-ness is required so distinct objects never collide.
• Prefix-free encoding lets you concatenate representations of several objects into one string while still recovering where each component starts and ends.
• A computational task is specified by a function; the same function can be computed by many different implementations.
• Cantor’s Theorem: the real numbers cannot be represented exactly as finite-length binary strings — the reals are uncountable.

Memory Tip: Keep asking “how would I unambiguously tell where this piece ends and the next begins?” whenever you compose representations — that question is exactly what prefix-free encoding answers.

Common Mistake: Assuming any encoding of a list of numbers works as long as each number is encoded correctly — without a prefix-free (or otherwise self-delimiting) scheme per component, concatenated representations become impossible to decode uniquely.

Important Questions:

• Why must a representation scheme be a one-to-one function? If two different objects mapped to the same binary string, a program reading that string could not tell which object it represents; requiring the encoding function E to be one-to-one guarantees every representable object has its own unique string, so decoding is always well defined.
• What does Cantor’s Theorem say, and why does it matter here? It says the real numbers cannot be represented exactly as finite binary strings, i.e. there is no one-to-one function from the reals to binary strings; this shows a limit on representation itself, separate from any question about algorithms, foreshadowing the book’s later results about the limits of computation.

Chapter 3: Defining Computation

Difficulty: Medium · Theory of Computation · Foundations · Key topics: Boolean circuits, NAND-CIRC, AND/OR/NOT, straight-line programs, equivalence of models

Defines computation precisely for the first time, using Boolean circuits — directed acyclic graphs of AND, OR and NOT gates — and their exact programming-language counterpart, straight-line programs with no loops. It shows circuits and straight-line programs are equivalent ways of describing the same computations, and that the NAND-CIRC language (built from a single NAND gate type) is equally powerful, since NAND alone can implement AND, OR, and NOT. The chapter traces the word “algorithm” to al-Khwarizmi and rewrites his 9th-century method for solving quadratic equations as a modern Python function. Boolean circuits are also treated as physical devices, since they can be built from transistors, mechanical parts, or even biological components.

Key Points:

• A Boolean circuit is a directed acyclic graph of AND, OR and NOT gates computing a finite function from n input bits to m output bits.
• A straight-line program has no loops, if-statements, or recursion; circuits and straight-line programs are equivalent ways to describe the same computation.
• The NAND-CIRC language has only one operation, foo = NAND(bar,blah), yet is exactly as powerful as circuits with AND/OR/NOT gates.
• Two computational models are equivalent when they can compute exactly the same set of functions — a “big idea” that recurs throughout the book.
• Boolean circuits can be physically realized with silicon transistors, mechanical parts, or even biological mechanisms.

Practice Tip: Trace a small NAND-CIRC program (3–4 lines) by hand on every input combination and build its truth table — seeing a handful of NAND gates reproduce AND, OR and NOT builds real intuition for why NAND alone is universal.

Common Mistake: Assuming a simpler gate set like NAND must be less powerful than AND/OR/NOT — equivalence here means equal computational power, not equal convenience; NAND-CIRC programs are just less pleasant to write, not weaker.

Important Questions:

• Why are Boolean circuits and straight-line programs considered equivalent models of computation? Every Boolean circuit can be translated line-by-line into a straight-line program, and every straight-line program can be translated back into a circuit; since each direction preserves the function computed, the two models can compute exactly the same class of functions, the book’s definition of equivalence.
• How can a language built from a single operation, NAND, compute the same things as one with AND, OR and NOT? NAND(a,b) can implement each of AND, OR and NOT using a few extra NAND gates (for example NOT(a) equals NAND(a,a)), so any circuit built from AND/OR/NOT gates can be rewritten as an equivalent circuit built only from NAND gates, showing the two gate sets have identical computational power.

Chapter 4: Syntactic Sugar, and Computing Every Function

Difficulty: Medium · Theory of Computation · Foundations · Key topics: syntactic sugar, procedures, conditionals, LOOKUP function, universality of finite functions

Shows how to extend the bare-bones NAND-CIRC language with higher-level features — user-defined procedures, conditional statements — by “syntactic sugar”: mechanically rewriting a program that uses a feature into an equivalent sugar-free program that doesn’t. It builds this toolkit up to construct the LOOKUP function (array indexing) in NAND-CIRC, then uses LOOKUP to prove the chapter’s main theorem: every finite function from n input bits to m output bits can be computed by some Boolean circuit. The chapter is explicit that this universal circuit can require exponentially many gates in the worst case, setting up the next chapter’s sharper gate-complexity question. An alternative, more direct proof of the same universality result is also given.

Key Points:

• Syntactic sugar means implementing a higher-level feature (procedures, if-statements) by mechanically rewriting programs that use it into equivalent programs in the original, feature-free language.
• Procedure definitions can be implemented in NAND-CIRC by “copy-paste”: inlining the procedure’s code at each call site, with variable renaming to avoid collisions.
• The universality theorem: every finite function f mapping n bits to m bits can be computed by some Boolean circuit (equivalently, some NAND-CIRC program).
• The circuit guaranteed by the universality theorem can require exponentially many gates in n — universality says nothing about efficiency.
• The LOOKUP function (given an index and an array, return the indexed entry) is a key building block used to prove universality.

Practice Tip: Implement the copy-paste procedure-inlining rule by hand on a 2-line “procedure” call — watching variable names get renamed to avoid collisions is the fastest way to internalize why syntactic sugar preserves correctness.

Common Mistake: Confusing “every function can be computed by some circuit” with “every function can be computed efficiently” — universality guarantees existence of a circuit, not a small one; some functions genuinely need exponentially many gates, as the next chapter proves.

Important Questions:

• What does “syntactic sugar” mean, and why doesn’t adding it change what a language can compute? It is a mechanical, purely syntactic transformation that rewrites a program using a convenient feature into an equivalent program in the original language without it, such as by inlining a procedure’s code; because the transformation always produces a program computing the exact same function, adding syntactic sugar can never let a language compute anything new.
• What does the universality theorem of this chapter claim, and what does it not claim? It claims that for every finite function f from n bits to m bits, there exists some Boolean circuit computing f exactly; it does not claim anything about how large that circuit needs to be — the theorem’s own construction can require a number of gates exponential in n, so universality is about existence, not efficiency.

Chapter 5: Code as Data, Data as Code

Difficulty: Hard · Theory of Computation · Foundations · Key topics: programs as strings, universal circuit, counting circuits, lower bounds, exponential gate complexity

Uses the fact that programs and circuits can themselves be represented as binary strings to prove two complementary results. First, by counting the number of distinct programs of a given length, it shows some functions require exponentially many gates to compute, complementing the previous chapter’s universality result with a genuine lower bound. Second, it constructs a “universal circuit”: a single circuit that, given the representation of any other circuit and an input, evaluates that circuit on that input. The chapter frames code-as-data as one of computing’s most fundamental ideas, underlying both general-purpose computers and phenomena like buffer-overflow security exploits, and notes that DNA is a natural, non-electronic example of the same duality.

Key Points:

• Any NAND-CIRC program of s lines can be represented as a binary string of length O(s log s), by renaming variables to a canonical form and prefix-free-encoding each line.
• Counting the number of distinct strings of a given length bounds the number of distinct programs of that length — since there are far more functions than short programs, most functions require large circuits.
• There exist functions requiring an exponential number of gates to compute; a universal circuit that evaluates other circuits is necessarily bigger than the circuits it evaluates.
• A universal circuit takes the string representation of another circuit plus an input, and outputs what that circuit would output — a “meta-circular evaluator” for circuits.
• The code/data duality (a program is just a string, so it can be fed as input to other programs) underlies general-purpose computing and is also the mechanism behind exploits like buffer overflows.

Memory Tip: Connect the counting argument to one sentence: there are only so many short strings, so if there are more functions than short strings, most functions cannot have short programs. That’s the whole lower-bound idea.

Common Mistake: Thinking hard-to-compute functions are some exotic edge case — the counting argument shows the overwhelming majority of functions on n bits require exponentially many gates; the functions we actually use (multiplication, sorting) are the rare, structured exceptions with small circuits.

Important Questions:

• How does counting programs of a given length prove that some functions need exponentially many gates? The number of NAND-CIRC programs of at most s lines is bounded by the number of binary strings of length O(s log s); since the number of functions from n bits to 1 bit is 2^(2^n), for s much smaller than exponential in n there are far fewer possible programs than functions, so most functions cannot be computed by any program of that size and must require exponentially many gates.
• What is a “universal circuit,” and why must it be larger than the circuits it evaluates? A universal circuit U takes the string representation of some other circuit C plus an input x, and outputs C(x), letting one fixed circuit simulate any other circuit given its description; because U must read and interpret C’s description as part of its computation, that overhead means U needs more gates than C itself, a limitation only overcome by moving to Turing machines and loops in the next chapter.

Part II: Infinite Computation

Chapter 6: Functions with Infinite Domains, Automata, and Regular Expressions

Difficulty: Medium · Theory of Computation · Infinite Computation · Key topics: unbounded-length inputs, infinite functions, XOR example, DFAs, regular expressions, pumping lemma

Extends the notion of a computational task beyond fixed-size Boolean circuits to functions with unbounded-length input, such as XOR, addition, or sorting, none of which can be computed by any single finite circuit. It distinguishes a function’s specification, which can be infinite even though describable in finitely many symbols, from its implementation, using the still-open Twin Prime Conjecture to show a function can be well-specified even when no known program computes it. The chapter then introduces deterministic finite automata (DFAs) as a restricted, always-terminating model for computing some unbounded-length functions, and proves the equivalence between DFA-computable functions and regular expressions.

Key Points:

• A function F mapping binary strings to binary strings is called “infinite” because its domain is unbounded, not because any single input is infinitely long.
• XOR, addition, multiplication, sorting and shortest-path are infinite functions that no single Boolean circuit can compute, though each fixed-length restriction can.
• A well-defined mathematical function can have a completely open specification/implementation gap — the TWINP function based on the Twin Prime Conjecture is well-defined regardless of whether anyone can compute it.
• A deterministic finite automaton (DFA) is a restricted model for unbounded-length input using only a constant amount of memory (its finite set of states).
• The functions computable by DFAs are exactly the functions describable by regular expressions — a foundational equivalence result.

Memory Tip: Remember the specification/implementation gap with the Twin Prime example — a function can be perfectly well-defined while it remains totally open whether anyone can compute it; being well-defined and being computable are different questions.

Common Mistake: Assuming that because XOR of n bits has a simple NAND-CIRC program for every fixed n, XOR itself is computable by “a circuit” — no single finite circuit handles every input length; a new circuit is needed for every n, exactly the limitation this chapter exists to fix.

Important Questions:

• Why can’t a Boolean circuit compute a function like XOR on strings of unbounded length? A Boolean circuit has a fixed number of input wires, so any single circuit accepts inputs of only one fixed length; XOR needs to accept inputs of every length, so a different circuit would be needed for every possible input length, which is not the same as one algorithm that works for all lengths.
• What is the relationship between deterministic finite automata and regular expressions? They are exactly equivalent: a function is computable by some DFA if and only if it can be described by some regular expression, meaning a state machine that reads one symbol at a time and a pattern built from concatenation, union and repetition define precisely the same class of functions.

Chapter 7: Loops and Infinity

Difficulty: Medium · Theory of Computation · Infinite Computation · Key topics: Turing machines, tape, states, transition function, NAND-TM, loops, palindrome example

Introduces the Turing machine, invented by Alan Turing in 1936 to formally capture what a human following a fixed set of rules with scratch paper can compute. It walks through the components of a Turing machine — a finite set of states, a tape divided into cells, and a transition function reading a symbol and deciding what to write, whether to move left, right or stay, and what state to enter next — and works a full example: an 11-state machine deciding whether a binary string is a palindrome. The chapter then introduces NAND-TM, obtained by adding loops and arrays to NAND-CIRC, and previews that Turing machines are equivalent to every general-purpose programming language. The core insight is that a finite instruction set, combined with looping, computes on inputs of arbitrary, unbounded length.

Key Points:

• A Turing machine reads and writes one tape cell at a time, using its current state and the symbol read to decide what to write, which direction to move, and its next state.
• The set of rules a Turing machine follows is called its transition function; a machine is fully specified by its tape alphabet and transition function.
• NAND-TM extends NAND-CIRC with loops and arrays, giving a programming-language model equivalent in power to Turing machines.
• An algorithm needs five ingredients: a finite instruction set, finite local state, unbounded working memory, a way to address memory, and a mechanism to decide when to loop versus halt.
• Turing machines and NAND-TM programs were designed to compute functions with unbounded-length input, something Boolean circuits cannot do.

Memory Tip: Picture Turing’s own description — a person with a pencil and an infinite roll of graph paper, who can only look at one square at a time, update their state of mind, and move one square left or right. Every Turing machine detail maps onto that picture.

Common Mistake: Thinking a Turing machine’s tape access is “random access” like an array — it is not; the head can only read/write the cell it currently points to and move one position at a time, so jumping far costs many steps, a limitation the RAM machine model in the next chapter removes.

Important Questions:

• What are the core components of a Turing machine, and what does each correspond to? A finite set of states (the “state of mind”), a tape divided into cells holding symbols from a finite alphabet (the “scratch paper”), a head that reads and writes one cell at a time and can move left, right, or stay, and a transition function that determines the new state, the symbol to write, and the direction to move; together these give a fixed, finite rule set capable of computing on inputs of any length.
• Why does the ability to loop matter for computing functions on unbounded-length inputs? A Boolean circuit has a fixed, finite number of gates and can only process a fixed amount of input; a loop lets a finite instruction set be executed repeatedly, with the number of repetitions depending on the actual input rather than being fixed in advance, exactly what is needed to process inputs of arbitrary length with one fixed algorithm.

Chapter 8: Equivalent Models of Computation

Difficulty: Medium · Theory of Computation · Infinite Computation · Key topics: RAM machines, NAND-RAM, cellular automata, lambda calculus, Church-Turing thesis

Proves that Turing machines are equivalent in power to a wide range of other models, a phenomenon called Turing equivalence. It introduces RAM machines (and their programming-language form, NAND-RAM), which more closely resemble real computer architecture by allowing direct, indexed access to any memory location, and proves the two models compute exactly the same functions. It extends the same equivalence to cellular automata (including Conway’s Game of Life, shown equivalent via the tool of Turing-machine “configurations,” reused later to prove Gödel’s Incompleteness Theorem) and to the lambda calculus, whose equivalence proof uses the “Y Combinator” technique to eliminate recursion. The chapter states the Church-Turing Thesis as the unifying principle behind all of these results.

Key Points:

• Two computational models are equivalent (Turing equivalent) if they can compute exactly the same set of functions; equivalence is proven by showing each model can simulate the other.
• RAM machines model computers with true random-access memory: a program can read or write any memory cell directly via an index, unlike a Turing machine’s tape.
• NAND-RAM extends NAND-TM with integer-valued variables, indexed array access, arithmetic operations, and native if/while — proven exactly equivalent in power to Turing machines.
• Cellular automata (like Conway’s Game of Life) — grids of simple cells following local rules based on their neighbors — are also Turing equivalent, proven using Turing machine “configurations.”
• The Church-Turing Thesis: every reasonable, general-purpose definition of “computable function” turns out equivalent to being computable by a Turing machine.

Memory Tip: Remember the chapter’s own phrase — equivalence lets us “have our cake and eat it too”: because all these models compute the same functions, you can always pick whichever model is most convenient for the proof at hand.

Common Mistake: Treating “RAM machines are equivalent to Turing machines” as meaning they run equally fast in practice — equivalence here is about which functions can be computed at all, not running time; a RAM machine’s O(1) random access genuinely is faster than a Turing machine’s O(n) tape-walking.

Important Questions:

• What is the key structural difference between Turing machines and RAM machines? A Turing machine can only read or write the single tape cell its head currently points to and must move one cell at a time to reach another location, while a RAM machine has indexed memory it can access directly in one step given an address; this matters for running time even though the two models are proven equivalent in what they can compute.
• What does the Church-Turing Thesis claim, and is it a mathematical theorem? It claims that every “reasonable” definition of an algorithm — Turing machines, RAM machines, the lambda calculus, or any standard programming language — ends up computing exactly the same class of functions; it is not a provable theorem, since “reasonable” is not itself a mathematical definition, but a widely believed thesis supported by every concrete model proposed so far turning out equivalent to Turing machines.

Chapter 9: Universality and Uncomputability

Difficulty: Hard · Theory of Computation · Infinite Computation · Key topics: universal Turing machine, halting problem, uncomputable functions, reductions, Rice’s theorem

Proves the existence of a universal Turing machine U that, given the description of any Turing machine M and an input x, simulates M running on x — even when M is more complex than U itself, unlike the universal circuit from an earlier chapter. It then uses this universal machine to prove one of the field’s most important results: the existence of uncomputable functions, with the Halting Problem as the canonical example. The chapter introduces reductions as the core technique for proving new uncomputability results, and closes with Rice’s Theorem, a “meta-tool” showing that essentially any nontrivial semantic property of programs is uncomputable, with direct implications for compilers and software verification.

Key Points:

• A universal Turing machine U satisfies U(M,x) = M(x) for every machine M and input x, including cases where M has more states or a larger alphabet than U itself.
• The Halting Problem — does M halt on input x? — is uncomputable: no algorithm can decide it correctly for every M and x.
• A reduction shows F is “no harder than” G by giving a way to compute F using a hypothetical algorithm for G; used in reverse, it shows that if F is uncomputable, G must be uncomputable too.
• Rice’s Theorem: every nontrivial semantic property of programs is uncomputable, not just the halting property specifically.
• The existence of a universal algorithm underlies general-purpose computers: instead of building new hardware for every task, you can feed new “software” to one fixed universal machine.

Memory Tip: Reductions feel backwards at first: read every reduction as “if G were solvable, so would already-known-unsolvable F be” — that’s the whole template for proving a new problem is hard.

Common Mistake: Assuming that because you can’t currently think of an algorithm for a problem, it must be genuinely uncomputable — the Halting Problem and Rice’s Theorem are proven uncomputable via rigorous arguments; most real problems are computable, just possibly hard, and calling something “uncomputable” requires an actual proof.

Important Questions:

• What makes the universal Turing machine more powerful than the universal circuit from the earlier chapter? The universal circuit always needed more gates than the circuit it simulated, so it could never simulate a strictly larger circuit; the universal Turing machine U reads a machine M’s description from the tape step by step rather than needing to contain all of M’s structure in advance, so U can simulate any Turing machine M, including ones with far more states than U has itself.
• How does a reduction let you prove a new function G is uncomputable using a function F you already know is uncomputable? You show that if there were a hypothetical algorithm for G, you could use it as a subroutine to build an algorithm for F; since F is already known uncomputable, no such algorithm for F can exist, so the assumed algorithm for G cannot exist either — uncomputability transfers from F to G through the reduction.

Chapter 10: Restricted Computational Models

Difficulty: Medium · Theory of Computation · Infinite Computation · Key topics: context-free grammars, pumping lemma, Turing completeness as a bug, DAO hack, decidable semantic properties

Argues that Turing completeness is not always desirable, since by Rice’s Theorem every nontrivial semantic question about a Turing-complete system’s behavior is uncomputable. It surveys real-world formalisms that accidentally turned out Turing complete (the C preprocessor, CSS, Magic: The Gathering, PostScript) and tells the story of the 2016 Ethereum DAO hack, where an attacker exploited the Turing-complete Solidity language to drain about 60 million dollars from a smart contract, forcing a controversial “hard fork” of the currency. It then introduces context-free grammars as a restricted, always-halting alternative used to specify programming-language syntax, working through arithmetic expressions as the canonical example.

Key Points:

• Turing completeness can be a liability: because Rice’s Theorem makes any nontrivial semantic question about a Turing-complete system uncomputable, unexpected Turing completeness creates real security and reliability risk.
• The 2016 Ethereum DAO hack exploited the Turing-completeness of the Solidity smart-contract language, draining about 60 million dollars and leading to a controversial currency “hard fork.”
• A context-free grammar (CFG) is a triple (V, R, s): variables V, rules R of the form v gives z, and an initial variable s; CFGs are the standard tool for specifying valid program syntax.
• Language designers deliberately avoid Turing-complete formalisms for syntax checking, so a compiler is guaranteed to always halt when deciding whether a program has a syntax error.
• Restricted models trade computational power for decidability: they compute a smaller class of functions, but unlike Turing-complete models, some of their semantic properties remain computable.

Memory Tip: Remember the DAO hack as the concrete cautionary tale for this chapter — “Turing complete” is not automatically a compliment; it means Rice’s Theorem applies, so no algorithm can fully verify what such a system will do on all inputs.

Common Mistake: Assuming context-free grammars can express any programming language’s full syntax — many real languages have context-sensitive rules (like requiring a variable to be declared before use) that a pure CFG cannot capture, which is why compilers combine CFG-based parsing with separate semantic-checking passes.

Important Questions:

• Why does Rice’s Theorem make Turing completeness risky in systems like CSS or smart-contract languages? Rice’s Theorem says every nontrivial semantic question about programs in a Turing-complete formalism is uncomputable in general; when a system turns out to be accidentally Turing complete, nobody can have an algorithm that verifies its behavior in advance, exactly the theoretical root of exploits like the DAO hack, where nobody could exhaustively check the smart contract’s behavior on all possible inputs.
• What is a context-free grammar, and why do language designers prefer it for defining syntax? A triple (V, R, s) of variables, rewrite rules of the form v gives z, and a start variable, used to recursively generate exactly the strings that count as syntactically valid; because CFGs are strictly weaker than Turing-complete models, a CFG-based parser is guaranteed to always halt when checking syntax, avoiding the risk that a Turing-complete syntax checker could loop forever.

Chapter 11: Is Every Theorem Provable?

Difficulty: Hard · Theory of Computation · Infinite Computation · Key topics: Gödel’s Incompleteness Theorem, proof systems, Hilbert’s program, unprovability

Shows that uncomputability results extend to a seemingly “computation-free” question: are all true mathematical statements provable? It formally defines a proof system as an algorithm V(x,w) that is effective (always halts with a yes/no verdict) and sound (never accepts a proof for a false statement). Using this definition and a deep connection between provability and computability, the chapter derives Gödel’s Incompleteness Theorem: for every sound proof system rich enough to express arithmetic, there exists a true statement the system cannot prove, refuting the early-20th-century Hilbert program’s goal of a complete axiomatic foundation for all of mathematics. Along the way it shows the uncomputability of the Halting Problem directly implies the existence of unprovable statements about Turing machines.

Key Points:

• A proof system for a set of “true” statements T is an algorithm V satisfying effectiveness (V(x,w) always halts with output 0 or 1) and soundness (V never outputs 1 for x not in T, regardless of the proof w offered).
• A proof system is complete if every true statement has some proof the system accepts; Gödel’s theorem shows no sufficiently rich, sound proof system can be complete.
• Gödel’s Incompleteness Theorem: for every sound proof system for sufficiently rich mathematical statements, there exists a statement that is true but not provable within that system.
• Gödel’s theorem dealt a devastating blow to Hilbert’s program, the early-1900s effort to derive all mathematical truths from a fixed set of axioms and inference rules.
• The uncomputability of the Halting Problem directly yields unprovable statements: whether a specific Turing machine halts can be true without any proof of that fact existing within a given formal system.

Memory Tip: Link the two chapters together in one sentence: uncomputable means “no algorithm can always decide it,” unprovable means “no proof system can always certify it” — Gödel’s theorem shows these are deeply the same phenomenon in disguise.

Common Mistake: Confusing “true but unprovable” with “false” or “just not yet proven by someone clever enough” — Gödel’s theorem is a fundamental limitation of any sufficiently powerful, sound, fixed proof system, not a temporary gap more effort within that same system could close.

Important Questions:

• What two conditions must an algorithm V satisfy to formally count as a “proof system”? Effectiveness, meaning V(x,w) must always halt and output 0 or 1 for every statement x and candidate proof w, and soundness, meaning if x is not actually true, V(x,w) must output 0 for every possible w, so no fake “proof” can ever trick the system into accepting a false statement.
• What did Gödel’s Incompleteness Theorem prove about Hilbert’s program? Hilbert’s program hoped all true mathematical statements could eventually be derived from a fixed set of axioms; Gödel proved that for any sound proof system rich enough to express basic arithmetic, some true statement necessarily exists that the system can never prove, showing a complete-and-consistent foundation for all of mathematics is mathematically impossible.

Part III: Efficient Computation

Chapter 12: Efficient Computation: An Informal Introduction

Difficulty: Easy · Theory of Computation · Complexity · Key topics: polynomial vs exponential time, shortest path, BFS, informal running time, threshold phenomenon

Informally surveys computational problems — shortest paths in graphs and others — to build intuition for the divide between problems with efficient (polynomial-time) algorithms and problems whose best known algorithms are exponential, before a formal definition of running time in the next chapter. It works through the shortest-path problem in detail, showing that although the number of paths between two vertices can be exponential, breadth-first search finds the shortest one in only O(m) time using a queue. The chapter frames running time as fundamentally a function of input length, not a single number, and highlights a recurring “threshold phenomenon”: many natural problems land either comfortably in low-degree polynomial time or provably need exponential time.

Key Points:

• Running time is a function of input length, not a fixed number — it only makes sense as how an algorithm’s time grows as input length n grows.
• Breadth-first search finds the shortest path between two vertices in O(m) time (m = number of edges) using a queue, despite there potentially being exponentially many total paths.
• The book focuses on the coarse distinction between polynomial time (O(n^c) for constant c) and exponential time, since this distinction is largely insensitive to the exact computational model chosen.
• Many natural problems show a “threshold phenomenon”: either a not-too-large polynomial algorithm exists, or the best known algorithm is exponential — genuinely intermediate cases are comparatively rare.
• This chapter deliberately uses an informal, “I know it when I see it” notion of running time; a fully rigorous definition is given in the next chapter.

Memory Tip: Anchor the chapter on one concrete number: shortest path via BFS costs O(m) time, yet the number of distinct paths between two vertices can be exponential — a clean example of why searching all solutions and finding the best algorithm are usually very different things.

Common Mistake: Treating “polynomial time” and “fast in practice” as synonyms — a polynomial-time algorithm with a huge exponent or constant can be slower in practice than an exponential algorithm on realistic input sizes; polynomial vs. exponential is about asymptotic scaling, not wall-clock speed on any one input.

Important Questions:

• Why can breadth-first search find the shortest path in O(m) time, even though the number of paths can be exponential? BFS never enumerates individual paths; it explores the graph outward from the start vertex one “layer” of distance at a time, visiting each vertex and edge at most a constant number of times using a queue, so its running time depends only on the graph’s size rather than on the number of paths, avoiding the exponential blowup that naive path-enumeration would hit.
• How do the book’s first three parts relate to one another, according to this chapter? Part I asked a quantitative question about finite functions (how many gates does a circuit need?); Part II asked a qualitative question about infinite functions (is this function computable at all?); Part III, beginning here, merges the two by asking how the resources needed to compute a function scale as its input length grows, the definition of running time formalized in the next chapter.

Chapter 13: Modeling Running Time

Difficulty: Hard · Theory of Computation · Complexity · Key topics: TIME(T(n)), the class P, the class EXP, time hierarchy theorem, P/poly, non-uniform computation

Gives the first fully rigorous definition of running time, defining a function F as computable in T(n) Turing-machine time if some machine halts within T(n) steps and outputs F(x) correctly for every sufficiently long input x. Using this, it formally defines the complexity classes P (polynomial time) and EXP (exponential time), proves the choice between Turing machines and RAM machines changes running time by at most a polynomial factor, and proves the Time Hierarchy Theorem: strictly more time genuinely buys strictly more computational power. It then connects this model back to the non-uniform circuits of Part I, defining the class P/poly of functions computable by a polynomial-size sequence of circuits, proving P is contained in P/poly, and showing P/poly even contains uncomputable functions.

Key Points:

• A function F is computable in T(n) TM-time if there exists a Turing machine that, for every sufficiently long input x, halts within T(n) steps and outputs F(x).
• P is the class of Boolean functions computable in polynomial time; EXP is the class computable in exponential time; P is a subset of EXP.
• Running time under Turing machines and under RAM machines (NAND-RAM) differ by at most a polynomial factor, so P and EXP are identical regardless of which of the two models defines them.
• The Time Hierarchy Theorem: for every k, there exist functions computable in O(n^(k+1)) time but not O(n^k) time — more time strictly buys more power, proving P is a proper subset of EXP.
• P/poly is the class of functions computable by a polynomial-size sequence of circuits (one circuit per input length); P is contained in P/poly, but P/poly even contains some uncomputable functions.

Memory Tip: Keep the two “sizes” straight: P/poly allows a different circuit for every input length, so it can bake in unlimited advice about each length separately — that’s exactly why it can contain functions no single uniform algorithm could ever compute.

Common Mistake: Treating P/poly as strictly stronger than P in a way that matters for real algorithms — its extra power comes entirely from allowing a different, possibly uncomputable, circuit-selection rule per input length, not from any circuit doing something a Turing machine couldn’t at that length.

Important Questions:

• What does the Time Hierarchy Theorem prove, and why does it matter for the P vs. EXP question? It proves that for every k, some function computable in O(n^(k+1)) time cannot be computed in O(n^k) time, meaning more time budget always buys the ability to compute strictly more functions; applying this with increasing exponents shows P cannot equal EXP, one of the few places in complexity theory where a strict separation is actually proven rather than conjectured.
• Why can the non-uniform class P/poly contain functions not computable by any algorithm at all? P/poly only requires that for each input length n, some polynomial-size circuit correctly computes the function restricted to that length, with no requirement that a single algorithm can produce the right circuit for each n; this lets P/poly encode an uncomputable function’s answers one input length at a time, so the class ends up strictly bigger than what any real algorithm could compute.

Chapter 14: Polynomial-Time Reductions

Difficulty: Medium · Theory of Computation · Complexity · Key topics: reductions, 3SAT, quadratic equations, longest path, maximum cut, no-harder-than relation

Introduces polynomial-time reductions as the central tool for relating the difficulty of different computational problems, building on the reduction technique from the uncomputability chapters but now in a running-time context. It formally defines F reduces to G to mean F can be computed by transforming an instance of F into an instance of G in polynomial time and then calling a hypothetical algorithm for G. The chapter demonstrates this on four seemingly unrelated hard search problems — 3SAT, quadratic equations, longest path, and maximum cut — by reducing 3SAT to each of the other three. This sets up the next chapter’s Cook-Levin Theorem, which completes the picture by reducing every one of these problems back to 3SAT.

Key Points:

• F reduces to G (F ≤p G) if there is a polynomial-time computable function R such that F(x) = G(R(x)) for every x — a polynomial-time algorithm for G then immediately gives one for F.
• 3SAT asks whether a 3CNF Boolean formula (an AND of clauses, each an OR of three literals) has a satisfying assignment; it is the chapter’s central starting point for reductions.
• All four problems discussed (3SAT, quadratic equations, longest path, maximum cut) are search problems with a trivial exponential-time brute-force algorithm and no known substantially faster algorithm.
• This chapter reduces 3SAT to the other three problems (one direction only) — showing each is at least as hard as 3SAT; proving true equivalence requires reductions in the other direction too, the next chapter’s job.
• If F reduces to G and G is in P, then F is in P — the formal justification for reading “F reduces to G” as “F is no harder than G.”

Practice Tip: Work through the theorem that a reduction plus a polynomial-time algorithm for G gives a polynomial-time algorithm for F on paper with concrete step counts — confirming that polynomial composed with polynomial stays polynomial removes the mystery from every reduction proof that follows.

Common Mistake: Reducing in the wrong direction — a common error is reducing G to F when the goal was to show F reduces to G; since F reduces to G says “F is no harder than G,” always double check which problem you’re assuming you already have a fast algorithm for.

Important Questions:

• What does it mean for one problem F to polynomial-time reduce to another problem G? There exists a polynomial-time computable transformation R that converts any instance x of F into an instance R(x) of G, such that F(x) equals G(R(x)); if there were a fast algorithm for G, you could build a fast algorithm for F by transforming the input with R and then running the algorithm for G, so F is no harder than G.
• Why doesn’t showing 3SAT reduces to maximum cut, by itself, prove the two problems are equivalent? F reduces to G is one-directional, showing F is no harder than G; proving two problems computationally equivalent requires reductions in both directions, so showing only 3SAT reduces to maximum cut establishes maximum cut is at least as hard as 3SAT but says nothing about the other direction, which the Cook-Levin Theorem supplies for 3SAT and every problem in NP at once.

Chapter 15: NP, NP Completeness, and the Cook-Levin Theorem

Difficulty: Hard · Theory of Computation · Complexity · Key topics: NP definition, certificates and witnesses, NP-completeness, Cook-Levin theorem, P vs NP

Defines the complexity class NP formally: a function F is in NP if there is a polynomial-time verifier V such that F(x)=1 exactly when some polynomially-sized certificate w makes V(x,w)=1, capturing problems whose solutions are easy to check even if hard to find. It proves the Cook-Levin Theorem, showing 3SAT is NP-complete: every problem in NP reduces to 3SAT in polynomial time, so a fast algorithm for 3SAT would instantly yield a fast algorithm for every problem in NP. The chapter frames the P vs NP question — whether every efficiently verifiable problem is also efficiently solvable — as one of the great open problems, and notes NP is asymmetric: nothing guarantees the complement of an NP problem is also in NP.

Key Points:

• F is in NP if there exists a polynomial-time algorithm V and polynomial bound such that F(x)=1 if and only if there exists a witness w of length polynomial in |x| with V(x,w)=1.
• “NP” historically stands for “non-deterministic polynomial time,” though the working definition used throughout the book is the certificate/witness definition above.
• 3SAT is NP-complete (the Cook-Levin Theorem): every problem in NP reduces to 3SAT in polynomial time, so if 3SAT has a polynomial-time algorithm, then P = NP.
• Thousands of real-world problems across mathematics, science and engineering have since been shown NP-complete by chaining reductions back to the Cook-Levin theorem.
• NP is not known (or believed) to be closed under complement: 3SAT being in NP does not imply “3SAT has no satisfying assignment” is also in NP.

Memory Tip: Keep the certificate framing front and center: a problem is in NP exactly when a proposed solution is easy to check, whether or not it’s easy to find; Gödel himself phrased P vs NP as asking whether a mathematician’s work of finding a proof could be fully replaced by a machine that just checks candidate proofs quickly.

Common Mistake: Confusing “F is in NP” with “F is hard” — NP contains both problems with known polynomial-time algorithms (like 2SAT) and problems believed to require exponential time (like 3SAT); membership in NP is only about the existence of an efficiently checkable certificate.

Important Questions:

• What is the formal definition of the class NP, in terms of certificates? F is in NP if there exists an integer a and a polynomial-time algorithm V such that for every input x, F(x)=1 if and only if there exists some string w of length at most |x|^a satisfying V(x,w)=1 — problems where, if the answer is yes, there is a short proof of that fact that can be verified quickly, even if finding it might be very hard.
• What does the Cook-Levin Theorem prove, and why is it so important? It proves 3SAT is NP-complete: every problem in NP can be reduced, in polynomial time, to 3SAT; if anyone ever found a polynomial-time algorithm for 3SAT, that algorithm (composed with the appropriate reduction) would immediately solve every problem in NP in polynomial time, which is why thousands of practical problems have since been proven NP-complete by reducing them to 3SAT or to each other.

Chapter 16: What if P Equals NP?

Difficulty: Medium · Theory of Computation · Complexity · Key topics: consequences of P=NP, search-to-decision reduction, optimization and learning, evidence for and against

Explores what would follow if someone proved P = NP, working from the assumption that 3SAT’s true complexity is either genuinely polynomial with a modest exponent, or genuinely exponential, rather than some awkward in-between case. Its central technical result is the search-to-decision reduction, proving that if P = NP, you could not only decide whether a solution exists for any NP problem, but efficiently find an actual solution by repeatedly querying a decision algorithm one bit of the answer at a time. The chapter surveys further consequences — efficient algorithms for optimization and learning problems, quantifier elimination, solving the polynomial hierarchy — and closes by weighing the evidence, noting the fastest known 3SAT algorithm still takes roughly 2^(0.35n) time while no one can rule out a 10n-gate circuit.

Key Points:

• The search-to-decision reduction: if P = NP, a polynomial-time algorithm exists not just to decide if a solution exists for any NP problem but to actually find one, by determining the solution one bit at a time.
• If P = NP, problems beyond NP decision problems become easy too, including many optimization and learning problems, quantifier elimination, and problems in the wider polynomial hierarchy.
• Current knowledge leaves an enormous gap for 3SAT: the fastest known algorithm takes about 2^(0.35n) time, while no one can rule out a circuit as small as 10n gates — a gap of roughly a factor of 10^100 for n=1000.
• The chapter’s working assumption is that 3SAT’s true complexity is one of two extremes — comfortably polynomial or genuinely exponential — rather than some intermediate case.
• Nearly all evidence gathered so far points toward 3SAT being exponentially hard (P not equal to NP), even though no proof of this exists.

Memory Tip: Hold onto the chapter’s own framing device — “3SAT is very easy” vs. “3SAT is very hard” as the two extreme, most-likely scenarios — whenever a P vs NP consequence feels abstract.

Common Mistake: Assuming that because nobody has proven 3SAT requires exponential time, its practical difficulty is somehow in doubt — essentially all evidence collected so far points toward exponential hardness; the P vs NP question remains formally open, but “open” does not mean “50/50.”

Important Questions:

• What does the search-to-decision reduction show? It shows that if P = NP, a polynomial-time algorithm for a decision problem can be turned into a polynomial-time algorithm for the corresponding search problem by fixing the answer bit by bit, querying whether a solution exists with each bit fixed in turn; this matters because most practically useful applications of an NP-complete problem are search problems, not just decision questions.
• What evidence does the chapter cite for believing 3SAT is exponentially hard rather than polynomial-time solvable? Decades of research on 3SAT algorithms have only reached roughly 2^(0.35n) time in the worst case, while nobody has proven even a circuit lower bound as small as 10n gates is impossible, leaving an enormous unresolved gap; the accumulated weight of failed attempts to find a fast algorithm, plus the extreme consequences a fast algorithm would have, is widely taken as strong evidence that P is not equal to NP.

Part IV: Advanced Topics

Chapter 18: Probability Theory 101

Difficulty: Medium · Theory of Computation · Advanced Topics · Key topics: sample space, events, random variables, expectation, independence, tail bounds

Reviews the probability theory needed for the rest of the book, built around the concrete sample space of tossing n independent, unbiased coins, represented as a uniformly random string of n bits. It defines events as subsets of this sample space, works through union and intersection with a worked induction proof that a random n-bit string has an even number of ones with probability exactly 1/2, and introduces random variables, expectation, independence and conditioning. The chapter explicitly limits its scope to what is needed for randomized algorithms — no named distributions, no hypothesis testing — though it stresses that even this simple coin-tossing setting can produce genuinely subtle reasoning, and previews Markov, Chebyshev and Chernoff tail bounds.

Key Points:

• The standard sample space throughout the book is tossing n independent, unbiased coins, modeled as choosing a string x uniformly at random from all n-bit strings.
• An event is a subset A of the sample space; its probability equals the fraction of all outcomes contained in A.
• A random n-bit string has an even number of 1’s with probability exactly 1/2, provable by induction on n by splitting the sample space into four equal-size sets based on parity and the last bit.
• Random variables assign a number to each outcome; expectation is their probability-weighted average, and independence describes when two events or random variables have no effect on each other.
• The chapter previews Markov, Chebyshev and Chernoff tail bounds — tools for bounding the probability a random variable strays far from its expected value, used constantly in later chapters.

Memory Tip: Anchor every probability calculation to the same picture — a string of n coin flips, each outcome equally likely — and translate the English description of any event into “which subset of outcomes does this correspond to?” before computing anything.

Common Mistake: Assuming everyday intuition about probability transfers automatically to formal calculations — the chapter is explicit that even independence and conditioning in the basic coin-tossing setting are subtle enough to trip up careful readers, so every claim should be checked against the formal definitions.

Important Questions:

• Why is “tossing n independent coins” used as the default sample space throughout the book? This setting is rich enough to model essentially every randomized algorithm the book studies, since a randomized algorithm’s random choices can always be encoded as some number of coin tosses, while being simple enough that events reduce to plain subset-counting; the n-coin case is sufficient for almost everything needed in the rest of the course.
• How is the fact “a random n-bit string has an even number of 1’s with probability 1/2” proved by induction? The base case n=1 is immediate; for the inductive step, the sample space is split into four equal-size quarters based on whether the first n-1 bits have an even or odd number of ones and whether the last bit is 0 or 1; the overall “even number of ones” event corresponds to exactly two of these four quarters, giving probability 1/2.

Chapter 19: Probabilistic Computation

Difficulty: Medium · Theory of Computation · Advanced Topics · Key topics: randomized algorithms, Monte Carlo, max-cut approximation, success amplification, worst-case guarantee

Shows, through concrete examples, that randomness can be a computational resource rather than just a nuisance, tracing the idea to Stanislaw Ulam and John von Neumann’s wartime “Monte Carlo” simulations for the atomic bomb project. Its main worked example is a randomized algorithm for the NP-hard maximum cut problem: assign each vertex to one side independently with probability 1/2, proven to cut at least half of all edges in expectation using linearity of expectation. The chapter stresses that a randomized algorithm’s guarantee holds for every possible input in the worst case, then introduces success amplification: since expectation alone doesn’t guarantee any single run succeeds, repeating the algorithm and keeping the best result drives the failure probability down.

Key Points:

• The term “Monte Carlo algorithm” originated as a wartime codeword coined by Ulam, von Neumann and collaborators for randomized neutron-transport simulations during the atomic bomb project.
• The random-cut algorithm for maximum cut (assign each vertex to a side independently with probability 1/2) cuts m/2 edges in expectation on any m-edge graph, proved via linearity of expectation.
• A randomized algorithm’s correctness guarantee is a worst-case guarantee over every possible input — the probability is taken only over the algorithm’s own random coin tosses, never over an assumed distribution on inputs.
• Expectation alone does not guarantee any single run succeeds; the random-cut algorithm is proven to succeed (cut at least m/2 edges) with probability at least 1/(2m) on any single run.
• Success amplification — repeating a randomized algorithm and keeping the best result — drives down the overall failure probability, a technique used throughout later chapters.

Memory Tip: Keep straight that “expected value” and “guaranteed outcome” are different things — the random-cut algorithm’s m/2-edges-in-expectation guarantee does not by itself say any single run gets close to m/2, which is exactly why the separate success-probability lemma is needed before amplification even makes sense.

Common Mistake: Thinking a randomized algorithm with a good expected-value guarantee is automatically reliable on any single run — the success probability for a single run of the basic max-cut algorithm can be as low as 1/(2m), which is why success amplification is a necessary extra step, not an optional nicety.

Important Questions:

• Why does the random-cut algorithm for maximum cut cut m/2 edges in expectation on every graph? For each edge, define an indicator variable that is 1 if the edge is cut; since each vertex is independently placed with probability 1/2, an edge is cut with probability exactly 1/2, so its expected contribution is 1/2; by linearity of expectation, the expected total number of edges cut is the sum over all m edges, giving m/2, and this holds for every graph, not just “typical” ones.
• What does it mean that a randomized algorithm’s guarantee is a worst-case guarantee? It means the probability bound holds for every single input the algorithm could ever be given, with the randomness coming entirely from the algorithm’s own coin tosses rather than any assumption the input was drawn at random; this is a much stronger guarantee than one that only holds for “average” inputs, since it cannot be broken by a cleverly chosen adversarial input.

Chapter 20: Modeling Randomized Computation

Difficulty: Hard · Theory of Computation · Advanced Topics · Key topics: the class BPP, the RAND operation, randomized Turing machines, amplification, pseudorandom generators

Formalizes the randomized algorithms of the previous chapter by adding a RAND() operation to the NAND-TM, NAND-RAM and NAND-CIRC languages, and defines randomized Turing machines whose transition function receives an extra random bit at every step. Using this, it defines BPP, the class of Boolean functions computable by a polynomial-time randomized algorithm that outputs the correct answer with probability at least 2/3 on every input, and proves this definition is robust under amplification. It places BPP in the complexity landscape — P is contained in BPP is contained in EXP, and BPP is contained in P/poly — and shows that if P = NP then BPP = P too, closing on pseudorandom generators as evidence that BPP might equal P even without resolving P vs NP.

Key Points:

• BPP contains every Boolean function F computable by a polynomial-time randomized algorithm that outputs F(x) correctly with probability at least 2/3, for every input, with probability taken only over the algorithm’s coin tosses.
• The precise success-probability threshold (2/3, 0.51, or 1 minus a tiny amount) does not change the class BPP, because amplification (repetition plus majority vote) can boost any constant success probability above 1/2 to any desired level.
• P is contained in BPP, BPP is contained in EXP, and BPP is contained in P/poly — placing randomized polynomial-time computation between deterministic polynomial time and non-uniform, circuit-based classes.
• If P = NP, then BPP = P as well, meaning resolving the P vs NP question would also settle whether randomness ever provides a genuine computational advantage over determinism.
• Pseudorandom generators, if they exist with strong enough parameters, would let every randomized algorithm be simulated deterministically with only a polynomial slowdown — concrete evidence that BPP might equal P.

Memory Tip: Remember BPP’s core sentence — it is still a worst-case class, exactly like the max-cut example in the previous chapter: the “probability at least 2/3” is taken only over the algorithm’s own coin tosses, on every possible input.

Common Mistake: Assuming the specific “2/3” in the definition of BPP is somehow a fundamental constant of computation — it is an arbitrary, convenient choice; swapping it for 0.51 or an even higher threshold yields the exact same class, since amplification converts one success threshold into another with only polynomial-time overhead.

Important Questions:

• Why doesn’t the exact success-probability threshold used to define BPP change which functions end up in the class? Given any polynomial-time randomized algorithm succeeding with probability just barely above 1/2, running it many independent times and taking the majority answer exponentially amplifies the success probability, because the chance the majority is wrong shrinks exponentially in the number of repetitions; since amplification only costs a polynomial time increase, any two reasonable thresholds end up defining exactly the same class.
• What connection does this chapter draw between the P vs NP question and the BPP vs P question? It shows that if P = NP, then BPP = P as well, so proving P = NP would automatically prove randomness gives no extra computational power beyond determinism; the separate question of whether BPP = P even without assuming P = NP is instead approached through pseudorandom generators, which would let randomized algorithms be derandomized if they exist with strong enough parameters.

Chapter 21: Cryptography

Difficulty: Medium · Theory of Computation · Advanced Topics · Key topics: perfect secrecy, one-time pad, computational security, public-key encryption, classical ciphers

Surveys cryptography’s central definitional achievement — a rigorous, mathematical definition of encryption security — against a backdrop of centuries of broken classical ciphers, from Mary Queen of Scots’ substitution cipher to the Vigenère cipher (unbroken for 300 years, then cracked by Babbage and Kasiski) to the Enigma machine defeated at Bletchley Park. It defines Claude Shannon’s notion of perfect secrecy and proves the one-time pad achieves it, then proves perfect secrecy’s fundamental limitation: it necessarily requires a key at least as long as the message. The chapter shows how relaxing to computational security — secure only against attackers with bounded computational resources — escapes this limitation and ties cryptography’s foundations directly to the P vs NP question, closing with a taste of public-key encryption.

Key Points:

• Perfect secrecy (Shannon, 1945): after intercepting a ciphertext, an attacker’s belief about which message was sent must be identical to their belief before interception.
• The one-time pad achieves perfect secrecy by combining the message with a truly random key exactly as long as the message, used only once.
• Perfect secrecy has a fundamental limitation: it provably requires a key at least as long as the message, making a one-time pad impractical to use at scale.
• Computational security relaxes perfect secrecy to only guard against computationally-bounded attackers, and its foundations are directly tied to the open P vs NP question and the existence of hard computational problems.
• Historical ciphers repeatedly failed by relying on security through obscurity rather than a rigorous security definition — the Vigenère cipher’s 300 years of presumed unbreakability ended once Kasiski published a systematic attack in 1863.

Memory Tip: Hold onto one sentence to distinguish the chapter’s two security notions: perfect secrecy assumes the attacker has unlimited computational power and still learns nothing, while computational security only promises a realistically bounded attacker learns nothing — that relaxation is what makes practical-length keys possible at all.

Common Mistake: Treating “this cipher hasn’t been broken yet” as equivalent to “this cipher is secure” — nearly every historical example (substitution ciphers, Vigenère, Enigma) was believed unbreakable for years before someone found the flaw; a rigorous security proof is categorically different from an absence of known attacks.

Important Questions:

• What is Shannon’s definition of perfect secrecy, and how does the one-time pad achieve it? It requires that after seeing the ciphertext, an attacker’s probability estimate for which message was sent must be exactly the same as before seeing anything; the one-time pad achieves this by combining the message with a truly random key of the same length, so for every possible message there exists some key that would have produced the exact same ciphertext, giving the attacker no information to favor one candidate message over another.
• Why can’t perfect secrecy be achieved with short, reusable keys, and how does computational security get around this? A theorem shows perfect secrecy necessarily requires as many possible keys as possible messages, meaning the key must be at least as long as the message and can never be reused; computational security escapes this by only defeating attackers whose computational resources are bounded, allowing short keys to remain secure as long as certain problems are assumed genuinely hard to solve efficiently.

Chapter 22: Quantum Computing

Difficulty: Hard · Theory of Computation · Advanced Topics · Key topics: double-slit experiment, quantum amplitudes, quantum circuits, the class BQP, Shor’s algorithm

Introduces the aspects of quantum mechanics most relevant to computation, starting from the double-slit experiment to show nature does not behave like a classical, deterministic system: photons passing through two open slits can produce fewer hits at some positions than when only one slit is open, impossible to explain with classical probability. It explains this using quantum amplitudes — numbers that, unlike probabilities, can be negative or complex, whose interference can cause classically-impossible cancellations, with observed probability equal to the squared magnitude of the amplitude. Building on this, the chapter defines the quantum circuit model and the complexity class BQP, and previews the ideas behind Shor’s Algorithm and the Quantum Fourier Transform, which let quantum computers threaten cryptography based on the hardness of factoring.

Key Points:

• The double-slit experiment shows classically-impossible destructive interference: some positions on the detector are hit less often with both slits open than with only one slit open.
• Quantum amplitudes are numbers (possibly negative or complex) whose squared magnitudes give observed probabilities; unlike probabilities, amplitudes can interfere constructively or destructively.
• BQP is the complexity class of functions computable efficiently (in polynomial time) by a quantum computer, defined via the quantum circuit model built on top of the classical models from earlier chapters.
• Shor’s Algorithm, using the Quantum Fourier Transform, gives an efficient quantum algorithm for integer factorization — a problem with no known efficient classical algorithm, and the basis of much of today’s public-key cryptography.
• No interpretation of quantum mechanics has gained universal scientific acceptance, and all of them make identical experimental predictions — the “shut up and calculate” approach sidesteps this open interpretive question entirely.

Memory Tip: Hold onto the chapter’s own baseball-versus-photon contrast: classical probabilities only ever add up, while quantum amplitudes can partially cancel each other out — the one-sentence version of why quantum mechanics cannot be modeled as ordinary randomness with extra steps.

Common Mistake: Describing a quantum computer as simply “trying every possibility at once” and brute-forcing exponentially many answers in parallel — this ignores that amplitudes can destructively interfere; a useful quantum algorithm must be designed so wrong-answer amplitudes cancel and the right-answer amplitude reinforces, which is why only a handful of problems currently have a known efficient quantum speedup.

Important Questions:

• What does the double-slit experiment demonstrate that a classical model of physics cannot explain? There are positions on the detecting wall hit when only the first slit is open, hit when only the second slit is open, but hit zero times when both slits are open simultaneously; under classical probability, opening a second path can only add more ways to reach a position, so this destructive interference cannot be explained by any classical probabilistic model and instead requires quantum amplitudes that can cancel.
• What is Shor’s Algorithm, and why does it matter for cryptography? An efficient quantum algorithm, built using the Quantum Fourier Transform, for factoring large integers into their prime factors; much of today’s public-key cryptography is secure specifically because no efficient classical factoring algorithm is known, so a sufficiently large working quantum computer running Shor’s Algorithm could break these schemes, which is why post-quantum cryptography has become an active research area.

Read or Download Introduction to Theoretical Computer Science for Free

This book is free from its official source — Boaz Barak publishes the complete set of chapters as HTML pages and a single combined PDF directly on introtcs.org, free for anyone to read or download. There is no separate paid edition; the legitimate free way to read or download the book is the official introtcs.org site below.

How to Study This Book

Part I, Foundations (Chapters 0–5), builds computation from the ground up using Boolean circuits and the single-operation NAND-CIRC language — work through Chapter 3’s circuit/straight-line-program equivalence and Chapter 4’s syntactic-sugar toolkit by hand before moving on, since every later part assumes you’re comfortable thinking in terms of gates and finite functions. Chapter 5’s counting-based lower bound (some functions need exponentially many gates) is the conceptually hardest chapter in this part.

Part II, Infinite Computation (Chapters 6–11), is where the book shifts from finite functions to unbounded-length inputs, introducing Turing machines in Chapter 7 as the book’s central computational model. Chapter 9 (universality and uncomputability, including the Halting Problem) and Chapter 11 (Gödel’s Incompleteness Theorem) are this part’s two hardest and most important chapters — both build directly on the reduction technique, so make sure that idea is solid before either one. Chapter 10 on restricted models (context-free grammars) can be read more lightly if your course skips formal language theory.

Part III, Efficient Computation (Chapters 12–16), formalizes running time and builds to the book’s best-known result, the Cook-Levin Theorem in Chapter 15. Read Chapter 12’s informal survey first for intuition, then Chapter 13’s formal running-time definitions, then Chapters 14–15 together since the reductions in Chapter 14 are only half the NP-completeness picture without Chapter 15’s Cook-Levin proof. Note that the book’s own Chapter 17 (space-bounded computation) exists only as an unfinished outline in the author’s source repository and is skipped on this page for that reason — see the FAQs below.

Part IV, Advanced Topics (Chapters 18–22), is a tour of randomization, cryptography and quantum computing built on everything before it. Chapter 18’s probability review is a prerequisite for Chapters 19–20, and Chapter 20’s formal definition of BPP is one of the more technical chapters in the book; Chapters 21 (cryptography) and 22 (quantum computing) can each be read as a self-contained capstone once Chapters 18–20 are solid, and either can be covered in either order.

The book itself is an active work in progress: two chapters that appear in its own table of contents (“Algorithms and society” and “Proofs and algorithms”) are, as of this writing, still just a one-line plan in the author’s source repository rather than finished chapters, so they are left out of the Chapter List below entirely rather than included as an empty, unfinished entry.

If your course runs short on time, Chapters 3, 7, 9, and 15 (Boolean circuits, Turing machines, uncomputability, and NP-completeness) form the conceptual spine most Theory of Computation courses actually test on; Chapters 5, 10, 11, and 22 are the ones most commonly trimmed to a lighter treatment when a semester is tight.

Used In These Programs

This book is used as a Theory of Computation course text, and as reference material, in BSCS coursework covering theoretical computer science, including Harvard’s own CS 121, the University of Virginia’s CS 3102, and UCLA’s CS 181. Browse all Computer Science category books.

Who Should Read This

Introduction to Theoretical Computer Science is written for students taking a Theory of Computation or Automata & Complexity course, typically in the second or third year of a computer science degree, after a first programming course and ideally alongside or after a discrete mathematics course. It assumes comfort with basic proof technique and mathematical notation, and builds computability and complexity theory entirely from first principles — from Boolean circuits through Turing machines, NP-completeness, randomization, cryptography, and a first taste of quantum computing. It is not a data-structures-and-algorithms text and assumes that material is already familiar; students who want a dedicated discrete-math and proof-technique foundation before starting this book are well served by a discrete mathematics for computer science textbook first.

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS programs with a Theory of Computation, Automata Theory, or Theoretical Computer Science core or elective course, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, GIKI, LUMS, and other HEC-recognized institutions, and for self-learners who want a free, rigorous, continuously updated theory-of-computation textbook built directly from an active Harvard course.

FAQs

Related Books

• Problem Solving with Algorithms and Data Structures using Python (the natural algorithmic complement — this book proves what can and can’t be computed efficiently, that book teaches how to actually design the algorithms)
• Think Python – Allen B. Downey (a gentle companion for students who want to implement the NAND-CIRC and Turing machine ideas in this book as actual running code)
• Data Structures in C++ – Aikman Series (the data-structures foundations this book assumes are already familiar)
• Think Java – Downey & Mayfield (a Java-based programming foundation for BSCS programs that pair a theory of computation course with an early Java-based sequence)

Introduction to Theoretical Computer Science by Boaz Barak is a free, rigorous, continuously updated theory of computation textbook — covering Boolean circuits, Turing machines, uncomputability, NP-completeness, randomization, cryptography and quantum computing in 22 chapters, published directly by the author at Harvard. Browse more Computer Science books for the rest of your semester.

Introduction to Theoretical Computer Science, by Boaz Barak (Harvard University). Work in progress, compiled December 6, 2023. Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0). Free to read online from its official source at https://introtcs.org/, with source files maintained at https://github.com/boazbk/tcs