CMSC 28100-1: Introduction to Complexity Theory

Class: Monday and Wednesday 2:30-3:50 pm in Ry 276

Tutorial: Friday 2:30-3:20 pm in Ry 276

Ketan Mulmuley
Ryerson 165-B, (773)702-1270

Office Hour: Monday 4-5 pm in Ry 165-B

Maia Fraser
Ryerson 178, (773)702-6614

Office Hour: Tuesday 12-1 pm in Ry 178.


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.


Introduction to Automata Theory, Languages, and Computation
by John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, 3rd edition, published by Addison Wesley, ISBN# 0321462253.


Will be posted here every Wednesday, due in class the following Wednesday.

Homework 1 (due Wednesday April 14th – in class) - solution

Homework 2 (due Wednesday April 21st – in class) - solution

Homework 3 (due Wednesday April 28th – in class) - solution

Homework 4 (due Wednesday May 12th – in class) - solution

Homework 5 (due Wednesday May 19th – in class) - solution

Homework 6 (due Wednesday May 26thin class) - solution

EXAM – Monday June 7th, 1:30pm to 3:30pm in Ry 276 – GOOD LUCK!!