18.404J / 6.840J Theory of Computation

Fall 2006

Venn diagram of some major computational complexity classes.
Computer scientists are still investigating whether some computational complexity classes of decision problems may in fact be equal. A famous open area in computer science is the "Does P=NP?" question: are all YES/NO problems that can be verified quickly (NP) actually problems that can be directly solved quickly (P)? The Clay Mathematics Institute offers a $1 million reward for a proof to this question. (Image courtesy of Kayla Jacobs.)

Course Highlights

This course features readings, assignments, and practice exams.

Course Description

This graduate level course is more extensive and theoretical treatment of the material in Computability, and Complexity (6.045J / 18.400J). Topics include Automata and Language Theory, Computability Theory, and Complexity Theory.

*Some translations represent previous versions of courses.

Donate Now

Staff

Instructor:
Prof. Michael Sipser

Course Meeting Times

Lectures:
Two sessions / week
1.5 hours / session

Recitations:
One session / week
1 hour / session

Level

Graduate

*Translations

Archived Courses

Previous version