Open Course Space

Automata, Computability, and Complexity

Massachusetts Institute of TechnologyUnited States6.045J
Free, no sign-up neededSpring 2011English
Go to course on MIT OpenCourseWare

This course provides a challenging introduction to some of the central ideas of theoretical computer science. Beginning in antiquity, the course will progress through finite automata, circuits and decision trees, Turing machines and computability, efficient algorithms and reducibility, the P versus NP problem, NP-completeness, the power of randomness, cryptography and one-way functions, computational learning theory, and quantum computing.

Description from MIT OpenCourseWare.

Where to take this course