CMSC 28100 / MATH 28100
Introduction to Complexity Theory
Spring 2009

General Information

Course: Introduction to Complexity Theory
Classes: MWF 11:30-12:20 Ry 276
Instructor: Ketan Mulmuley
Office Hour: Wednesday 3:30-4:30 PM Ry 165B
Teaching Asst: Ankan Saha
Tutorial/OH: Monday 5-6 PM Ry 257


Computability topics are discussed, including the s-m-n theorem, the recursion theorem and resource-bounded computation. This course introduces complexity theory. Relationships between space and time, determinism and nondeterminism, NP-completeness, and the P versus NP question are investigated.


The text is available from the Seminary Co-op Bookstore.
Title: Introduction to Automata Theory, Languages, and Computation, 3rd edition
Authors: John Hopcroft, Rajeev Motwani, and Jeffrey Ullman
Publisher: Addison-Wesley


Last revised: April 1, 2009.