Open Course Space

Theory of Computation

Massachusetts Institute of TechnologyUnited States18.404J
Free, no sign-up neededFall 2020English
Go to course on MIT OpenCourseWare

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.

Description from MIT OpenCourseWare.

Where to take this course