0

(

ratings

)

1

students

Created by:

Profile Photo

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

Profile Photo
Massachusetts Institute of Technology