198:509: Foundations of Computer Science
Meeting times and location: Mondays and Wednesdays in Beck Hall 252 (Livingston); 3:20--4:40
Phone: (848) 445-7296
FAX: (732) 445-0537
Office: Hill 442
Click here for current
Grader: Harsha Srimath Tirumala
The text for the class is:
Theory of Computation
by Dexter Kozen.
It appears that the book is also available in
Here is information about
errata in the textbook. Let me know about additional
errors as you discover them.
We will also augment with some material on
Kolmogorov complexity, by Lance Fortnow.
Click here to find out about what was covered in class, and what material you should read next.
(Topics will be covered in a different order.)
- Basic Notions (Chapters 1-3)
- Small Space Classes, Reducibility, and Completeness (Chapters 4-6)
- Alternation, PSPACE, and the Polynomial Hierarchy (Chapters 7-10)
- Basics (Chapter E)
- Complexity of Logical Theories (Chapters 21-24, and B)
- Second-Order Logic (Chapters 25-27) [If there is time.]
- Undecidability, Incompleteness
- Basics, Recursion Theorem (Chapters 33-34)
- The Arithmetic Hierarchy (Chapters 35-36)
- Incomplete Degrees (Chapters 37-38)
- Kolmogorov Complexity
- Possible Other Topics
- Probabilistic Computation (Chapters 13 and 14)
- #P and Toda's Theorm (Chapters F and G)
- Berlekamp's Factorization Algorithm (Chapters B & D)
- The Gap and Speed-Up Theorems (Chapter 32)
- Abstract Complexity (Chapter J)
- The Analytic Hierarchy and Applications (Chapters 39-41)
- Various Topics in Complexity (Various Chapters)
Completeness Theorem: Every valid statement has a proof (Notes)
There will be one midterm and one (take-home) final.
will be held in class.
In addition, there will
be homework every two or three lectures; this homework is a major consideration
in assigning grades.