6.045/18.400  Automata, Computability, & Complexity - Great Ideas in Theoretical Computer Science

This course provides a challenging introduction to some of the central ideas of theoretical computer science.  Beginning in antiquity, the course will progress through circuits and decision trees, finite automata, 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.  It examines the classes of problems that can and cannot be solved by various kinds of machines.  It tries to explain the key differences between computational models that affect their power.

Prerequisites: We assume that you have taken 6.042 Mathematics for Computer Science, or have equivalent mathematical preparation.  In particular, we will assume you have basic "mathematical maturity": i.e., that you're comfortable both reading and writing rigorous mathematical proofs.

Relation to other courses: For Spring 2009 this course is a combination of the traditional version of 6.045 that has been taught in the past and the Spring 2008 Special Subject course 6.080 "Great Ideas in Theoretical Computer Science". There is significant overlap between 6.045 and 6.840. However, as a graduate course, 6.840 is able to cover topics in much more mathematical depth.

Please see the syllabus for more information.