6.045/18.400 Automata, Computability, and Complexity

Course Home Page Objectives and Outcomes Contact Info General Information/Policies Calendar Course Materials by Lecture Date

March 2007
Sunday	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday
				1 Recitation 4: Quiz Questions and Automata Wrap-up	2	3
4	5 Lecture 8: Introduction to computability. Basic Turing machines. Some variations.	6	7 Lecture 9:Decidable languages vs. recognizable languages. Enumerable languages. Nondeterministic Turing machines. Turing machines that answer questions about FAs and regular expressions.	8 Recitation 5: Turing Machines	9	10
11	12 Lecture 10: Undecidability. The Halting Problem. A non-Turing-recognizable language.	13	14 Lecture 11: Undecidability. Computation histories. Post Correspondence Problem.	15 Recitation 6: Undecidibility	16	17
18	19 Lecture 12: Undecidability. Counter machines. Stack machines.	20	21 Lecture 13: Computable functions. Mapping reducibility. Applications of mapping reducibility to show undecidability and non-recognizability. Rice's Theorem. Applications of Rice's Theorem to show undecidability.	22 Recitation 7: Reducibility, Rice's Theorem and Recursion Theorem	23	24
25	26 Spring Vacation	27 Spring Vacation	28 Spring Vacation	29 Spring Vacation	30 Spring Vacation	31 Spring Vacation

April 2007
Sunday	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday
1	2 Lecture 14:Self-referencing machines. The Recursion Theorem. Applications of the Recursion Theorem.	3	4 Lecture 15: Quiz 2. Covers material from classes 8-14.	5 Recitation 8: Quiz 2 Questions and Computability Wrap-up	6	7
8	9 Lecture 16:Complexity theory. Time complexity analysis. Asymptotic function notation. Time complexity classes. P, Polynomial time.	10	11 Lecture 17:Hierarchy theorems. NP, Nondeterministic Polynomial time. Examples of NP problems. P vs. NP.	12 Recitation 9: P vs NP.	13	14
15	16 No Class (Patriots Day)	17	18 Lecture 18: Polynomial-time reducibility. Examples: Clique and Vertex Cover. NP-completeness.	19 Recitation 10: Poly-Time Reductions	20	21
22	23 Lecture 19: SAT is NP-complete. 3SAT, CLIQUE are NP-complete.	24	25 Lecture 20: More NP-complete problems. Traveling Salesman, Multiprocessor Scheduling,...	26 Recitation 11: NP-Completeness	27	28
29	30 Lecture 21: Still more NP-complete problems. Survey of other topics in computability: Optimization vs. decision problems. Higher-order complexity classes. Oracle complexity classes.

May 2007
Sunday	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday
		1	2 Lecture 22: Quiz 3. Covers material from classes 16-21.	3 Recitation 12: Quiz 3 Questions and End of Time-Complexity	4	5
6	7 Lecture 23: Space complexity. Deterministic vs. nondeterministic space complexity classes (Savitch's Theorem). Polynomial space and Pspace-completeness. TQBF. TQBF is Pspace-complete.	8	9 Lecture 24: L, Log space. NL, Nondeterministic Log space. Extension of Savitch's theorem to smaller space bounds. Log space reducibility and NL-completeness. PATH is NL-complete. NL vs. P and coNL.	10 Recitation 13: Space Complexity III	11	12
13	14 Lecture 25: Probabilistic Turing machines. PPT Turing machines. Probabilistic time complexity classes, BPP and RP. Example: Primality testing.	15	16 Last class Lecture 26: Probabilistic time complexity classes. Example: Branching-program equivalence. Relationships among classes. Wrapup.	17 Last recitations Recitation 14: Probabilistic Complexity and Interactive Proofs	18	19
20	21	22	23	24	25	26
27	28	29	30	31