- 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]. (Covered Lemma 22.3.) 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: Continuing with the Reals with addition [Lecture 22]. See the comment above about errata in the textbook.
- Oct. 30: Hardness for the Reals with addition; up through Lemma 23.1. [Lecture 23].
- Nov. 1: Finish with Hardness for the Reals with addition [Lecture 23]. Start of hardness for the Naturals with addition [Lecture 24].
- Nov. 6: Chinese Remaindering [Supplementary Lecture B]. Finish with Pressburger Arithmetic [Lecture 24]. Began a discussion of the Recursion Theorem [Lectures 33-34]. As a sidelight: Quines (you may want to look at the Quine Page).
- Nov. 8: The Recursion Theorem [Lectures 33-34]. (See Notes on using the Recursion Theorem to prove the stronger form of the Incompleteness Theorem.) Other applications: Rice's Theorem. [Lectures 33-34].
- Nov. 13: More applications of the Recursion Theorem: the set of "minimal indices" is immune [Lectures 33-34]. Kolmogorov Complexity [notes; see home page]; many examples of true statements that have no proof.
- Nov. 15: Applications of Kolmogorov complexity. See Notes on using Kolmogorov complexity to prove results about primes. Time-bounded Kolmogorov complexity.
- Nov. 20: Relativized Complexity [Lecture 28]. Begin Probabilistic Computation [Lectures 13 and 14]; PIT is in coRP (assuming the Schwartz-Zippel Lemma, which was not proved).
- Nov. 27: The Swartz-Zippel Lemma; BPP is contained in P/poly.
- Nov. 29: More on Probabilistic Computation; BPP is in the polynomial hierarchy [Lectures 13 and 14]. EXPSPACE is not in P/poly. If NP is in P/poly, then PH collapses.
- Dec. 4: Parallel Complexity Classes [Lectures 11-12].
- Dec. 6: Finite Model Theory, Expressiveness of Logics
- Dec. 11: By request: The Piano-Mover's Problem is PSPACE-complete. A discussion of quantum computation; presentation of the algorithm BPP-reducing factoring to "order-finding", and analysis of correctness.
- Dec. 13: Analysis of the error probability for the reduction of factoring to order-finding.