Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

# Theory of Computation

### Overview

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.

### Syllabus

• 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

### Taught by

Prof. Michael Sipser

## Reviews

Start your review of Theory of Computation

### Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.