Translations*
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.)

Level:

Graduate

Instructors:

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.