Foundations of Computer Science
Here is a brief summary of what was covered each day, along with an
indication of what I plan to cover in the next lecture.
- 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,
- 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
- 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.
- 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
- 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
In particular, note that Lemma 22.4 should be
- 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: