0
(
ratings
)
1
students
Created by:
Last updated:
September 23, 2022
Duration:
Unlimited Duration
FREE
This course includes:
Unlimited Duration
Badge on Completion
Certificate of completion
Unlimited Duration
Description
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.
Course Curriculum
- Introduction, Finite Automata, Regular Expressions Unlimited
- Nondeterminism, Closure Properties, Regular Expressions → Finite Automata Unlimited
- The Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs Unlimited
- Pushdown Automata, CFG ↔ PDA Unlimited
- The CF Pumping Lemma, Turing Machines Unlimited
- TM Variants, the Church-Turing Thesis Unlimited
- Decision Problems for Automata and Grammars Unlimited
- Undecidability Unlimited
- Reducibility Unlimited
- The Computation History Method Unlimited
- The Recursion Theorem and Logic Unlimited
- Time Complexity Unlimited
- P and NP, SAT, Poly-time Reducibility Unlimited
- NP-Completeness Unlimited
- Cook-Levin Theorem Unlimited
- Space Complexity, PSPACE, Savitch’s Theorem Unlimited
- PSPACE-Completeness Unlimited
- Games, Generalized Geography Unlimited
- L and NL, NL = coNL Unlimited
- Hierarchy Theorems Unlimited
- Provably Intractable Problems, Oracles Unlimited
- Probabilistic Computation, BPP Unlimited
- Probabilistic Computation (cont.) Unlimited
- Interactive Proof Systems, IP Unlimited
- coNP ⊆ IP Unlimited
About the instructor
5
5
Instructor Rating
1
Reviews
1520
Courses
1913
Students
Massachusetts Institute of Technology