This is an MIT OpenCourseWare course taught by Professor Michael Sipser. Includes instructor insights, readings, lecture notes, video lectures, assignments, and exams.
Course 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.”