Theory of Computation

This course emphasizes computability and computational complexity theory. Topics include regular and context-free languages, decidable and undecidable problems, reducibility, recursive function theory, time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.

• Lecture 1: Introduction, Finite Automata, Regular Expressions
• Lecture 2: Nondeterminism, Closure Properties, Regular Expressions → Finite Automata
• Lecture 3: Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs
• Lecture 4: Pushdown Automata, CFG ↔ PDA
• Lecture 5: CF Pumping Lemma, Turing Machines
• Lecture 6: TM Variants, Church-Turing Thesis
• Lecture 7: Decision Problems for Automata and Grammars
• Lecture 8: Undecidability
• Lecture 9: Reducibility
• Lecture 10: Computation History Method
• Lecture 11: Recursion Theorem and Logic
• Lecture 12: Time Complexity
• Lecture 14: P and NP, SAT, Poly-Time Reducibility
• Lecture 15: NP-Completeness
• Lecture 16: Cook-Levin Theorem
• Lecture 17: Space Complexity, PSPACE, Savitch's Theorem
• Lecture 18: PSPACE-Completeness
• Lecture 19: Games, Generalized Geography
• Lecture 20: L and NL, NL = coNL
• Lecture 21: Hierarchy Theorems
• Lecture 22: Provably Intractable Problems, Oracles
• Lecture 23: Probabilistic Computation, BPP
• Lecture 24: Probabilistic Computation (cont.)
• Lecture 25: Interactive Proof Systems, IP
• Lecture 26: coNP ⊆ IP