- Sept. 6: Administrivia, Modeling computation, start of computability theory, r.e. sets, decidability. [Lecture 1, but not including the "Crossing Sequences" section] [Lectures 33 (pp. 220-221) and 35 (in part).] This material may also be useful: Computable sets, Undecidable problems, r.e. sets
- Sept. 11: Gödel's incompleteness theorem. Also, [Supplementary Lecture E]. Structures, truth, validity. Syntax vs semantics. Proof systems; Peano Arithmetic. A brief discussion of Gödel's completeness theorem. Encodings of valid computations. HP m-reduces to the first-order theory of the Natural Numbers.
- Sept. 13: HP m-reduces to the set of Theorems of Peano Arithmetic. More from [Supplementary Lecture E]: terms, valuations, prenex form, etc. Brief discussion of non-standard models and compactness. Brief introduction to complexity classes (DTIME and DSPACE). [Lectures 1,2,3].
- Sept. 18: Computational Complexity DTIME, NTIME, DSPACE, NSPACE, and the canonical complexity classes. Examples of nondeterministic computations for connectivity in graphs and for SAT. NTIME(t) is contained in DSPACE(t), NSPACE(t) is contained in DTIME(2^O(t)). Space-bounded computations can be assumed to halt, due to the limited number of space-bounded configurations. [Lectures 1,2,3].
- Sept. 20: Savitch's Theorem. Separation results (diagonalization). Translational methods. [Lectures 2-3].
- Sept. 25: The Immerman-Szelepcsenyi Theorem [Lecture 4]. Hardness and completeness, reducibility. Hardness implies lower bounds on complexity.
- Sept. 27: Logspace reducibility is transitive; complete problems for NL, P, and NP. [Lectures 5 and 6]
- Oct. 2: Alternation [Lecture 7]
- Oct. 4: Finish with Alternation; show DTIME(t) is in ASPACE(log t). The Polynomial Hierarchy [Lectures 9-10]
- Oct. 9: PSPACE complete problems [Lecture 8].
- Oct. 11: Review for the midterm. Translational methods: (There is a unary language in NP-P iff DTIME(2^O(n)) is not equal to NTIME(2^O(n)).) The NTIME hierarchy theorem (see notes ).
- Oct. 16: Midterm examination (closed book; closed notes).
- Oct. 18: Start of decidable theories; isomorphism of any two countable models for the theory of dense linear orders without endpoints, and the PSPACE upper bound for this theory [Lecture 21]. Start of the discussion of the upper bound on the complexity of the theory of the Reals with addition [Lecture 22].
- Oct. 23: Reals with addition [Lecture 22]. Note that there are some errors in Lecture 22. See the errata page In particular, note that Lemma 22.4 should be restated.
- Oct. 25:
- Oct. 30:
- Nov. 1:
- Nov. 6:
- Nov. 8:
- Nov. 13:
- Nov. 15:
- Nov. 20:
- Nov. 27:
- Nov. 29:
- Dec. 4:
- Dec. 6:
- Dec. 11:
- Dec. 13: