Archived Versions

18.404J / 6.840J Theory of Computation

As taught in: 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.)




Prof. Michael Sipser

Course Features

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.