MIT 6.045J - Automata, Computability, Complexity
Taught by Prof. Scott Aaronson
Course Description
This course provides a challenging introduction to some of the central ideas of theoretical computer science. It attempts to present a vision of “computer science beyond computers”: that is, CS as a set of mathematical tools for understanding complex systems such as universes and minds. Beginning in antiquity, with Euclid’s algorithm and other ancient examples of computational thinking, the course will progress rapidly through finite automata, Turing machines and computability, decision trees and other concrete computational models, efficient algorithms and reducibility, NP-completeness, the P versus NP problem, the power of randomness, cryptography and one-way functions, computational learning theory, interactive proofs, and quantum computing and the physical limits of computation. Class participation is important, as the class will include discussion and debate about many of these topics.
Course website
Lecture Videos (YouTube)