198:509 Foundations of Computer Science - Fall 2012
This is an introductory graduate course on computability, logic and complexity theory. For the most part we will follow the previous versions of the course from
Fall 2010 and
Fall 2011. The text for the class is
Theory of Computation by Dexter Kozen. We will also use the following
notes by
Madhavan Mukund and
S P Suresh for the lectures on logic and
Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak for the lectures on complexity theory.
Who, When, Where
Raghu Meka, email: raghu@ias.edu, Office: CoRE 413
Class timings: Thu 12 - 3, Hill 250
Office hours: Thu 10 - 11
Grading
One midterm (10/25/2012 - 20%) and one final (30%)
Five or six assignments (will be posted here). For each assignment, you have a week from the date you receive the graded assignments to have them re-evaluated for an additional 50% of the original credit for problems you got wrong, i.e., your final score for a problem after resubmission will be old_score+.5*max(0,new_score-old_score).
Assignments
Assignment 0 (Out - 09/06/12; In - not to be turned in)
Assignment 1 (Out - 09/20/12; In - 10/04/12);
Solutions
Assignment 2 (Out - 10/04/12; In - 10/18/12);
Solutions
Midterm (10/25/12);
Solutions
Assignment 3 (Out - 11/08/12; In - 11/15/12);
Solutions
Assignment 4 (Out - 11/20/12; In - 11/29/12);
Solutions
Assignment 5 (Out - 11/29/12; In - 12/06/12);
Solutions
Final on 12/13/12. Open book and includes all topics covered in class.
Lecture Summaries (click Abstract for summary)
Lecture 1 - 09/06/12
Review of basic Turing machine concepts: diagonalization, reductions, closure properties. See Lectures 6 and 7
here for similar material.
ABSTRACT
We reviewed basic concepts of Turing machines. I did not formally define Turing machines, but you should take a look at the formal definition and become comfortable with using "pseudocode" descriptions (which are easier to reason about) instead of formal Turing machine descriptions. We showed that the Halting problem is undecidable, saw the use of Turing machine reductions and looked at closure properties of decidability and Turing recognizability. Take a look at Homework 0 (not to be turned in) which is meant to review the basics of Turing machines.
Lecture 2 - 09/13/12
Review of basic Turing machine concepts. Godel numbering and Kleene's recursion theorem. See Lecture 33 from text.
ABSTRACT
We reviewed the review of Turing machines from last class. We looked at Godel numbering, saw an example of it and worked out some computability properties of the numbering. Finally, we saw Kleene's recursion theorem and its proof. We will go over the proof once again in next class.
Lecture 3 - 09/20/12
Review of Kleene's recursion theorem and its applications. Introduction to arithmetic hierarchy. See lectures 34, 36 from text.
ABSTRACT
We reviewed the proof of Kleene's recursion theorem. Saw applications of the theorem to existence of 'Quines' and a proof of Rice's theorem. We then introduced the arithmetic hierarchy and looked at the notions of many-one Turing reducibility and completeness under this notion.
Lecture 4 - 09/27/12
Introduction to complexity theory - basic complexity classes and relations between them. See lectures 1 and 2 from text.
ABSTRACT
We introduced turing machines and non-deterministic turing machines more formally. Then, defined basic time and space complexity classes (P, NP, PSPACE, etc.,) and saw basic relations between them ending with NSPACE(S(n)) is contained in DTIME(2^{O(S(n))}).
Lecture 5 - 10/04/12
Savitch's Theorem. Space Hierarchy theorem. Padding arguments. See lecture 3 from text. Assignment 2 out.
ABSTRACT
We proved Savitch's theorem that NSPACE(S(n)) is in DSPACE(S(n)^2). We then proved a hierarchy theorem for deterministic space Turing machines and saw a simple case of non-deterministic space hierarchy by using a padding argument along with deterministic space hierarchy.
Lecture 6 - 10/11/12
Immerman-Szelepcsenyi Theorem. P, NP, NP-Completeness, Karp reductions. See lecture 4 from text and chapter 2 of Arora-Barak text.
ABSTRACT
We proved Immerman-Szelepcsenyi theorem that NSPACE(S(n)) = co-NSPACE(S(n)). We then revisited the class NP and saw an equivalent definition in terms of 'efficient verifiability'. We stated Cook-Levin theorem and used it to show that 3SAT and INDEP-SET are NP-Complete. Next week, we will prove the Cook-Levin theorem. For this part of the course we will follow the Arora-Barak text. Assignment 1 was returned in class.
Lecture 7 - 10/18/12
Cook-Levin theorem. Midterm review. See chapter 2 of Arora-Barak text.
ABSTRACT
Cook-Levin theorem. Midterm review.
Lecture 10/25/12: Midterm. Lecture 11/01/12: Canceled (Sandy)
Lecture 8 - 11/08/12
Introduction to Interactive Proofs - IP, AM and statement of PCP theorem. Chapter 8 in Arora, Barak.
ABSTRACT
Basic definitions of the classes without proofs. Interactive proof of Graph-Nonisomorphism.
Lecture 9 - 11/15/12
Introduction to randomized computation, RP, BPP. Randomized algorithms and amplification. Chapter 7 in Arora, Barak .
ABSTRACT
Definitions of RP, BPP. Fingerprinting, perfect matching, error amplification. Assignment 3 in.
Lecture 10 - 11/20/12
Introduction to Logic. First chapter of lecture notes. Assignment 4 out.
ABSTRACT
Definitions of propositional logic, deduction rules, completeness and soundness. We also reviewed some questions from the midterm.
Lecture 11 - 11/29/12
More propositional logic. First chapter of lecture notes. Assignment 5 out.
ABSTRACT
Strong completeness for propositional logic and basic definitions and examples of first order and second order logics.
Lecture 12 - 12/06/12
Proof Systems, DPLL algorithm and Review.
ABSTRACT
Resolution proof systems and DPLL algorithm for satisfiability and finding proofs in propositional logic. Review for final.
Syllabus
Computability
Basics, Recursion Theorem (Lectures 33-34)
Arithmetic Hierarchy (Lectures 35-36)
Post's Problem (Lectures 37-38)
Logic
Basics, Propositional Logic (Chapter 1)
First Order Logic - Completeness, Undecidability (Chapter 4)
The Incompleteness Theorem