1
This course emphasizes computability and computational complexity theory.
FREE
This course includes
Hours of videos
694 years, 4 months
Units & Quizzes
25
Unlimited Lifetime access
Access on mobile app
Certificate of Completion
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 Currilcum
- 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
