Foundations of Computer Science
198:509
Fall, 2017
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,
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.