CMSC 281001: Introduction to
Complexity Theory
Class: Monday
and Wednesday 2:303:50 pm in Ry 276
Tutorial:
Friday 2:303:20 pm in Ry 276
Instructor: Ketan
Mulmuley Ryerson 165B, (773)7021270
mulmuley@cs.uchicago.edu
Office Hour: Monday
45 pm in Ry 165B

TA: Maia
Fraser Ryerson 178, (773)7026614 maia@cs.uchicago.edu
Office Hour: Tuesday
121 pm in Ry 178.

Overview:
Computability
topics are discussed, including the smn theorem, the
recursion theorem and resourcebounded computation. This course
introduces complexity theory. Relationships between space and
time, determinism and nondeterminism, NPcompleteness, and the
P versus NP question are investigated.
Text:

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

Assignments:

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

Homework 1 (due Wednesday April 14^{th}
– in class)  solution

Homework 2 (due Wednesday April 21^{st}
– in class)  solution

Homework 3 (due Wednesday April 28^{th}
– in class)  solution

Homework 4 (due Wednesday May 12^{th}
– in class)  solution

Homework 5 (due Wednesday May 19^{th}
– in class)  solution

Homework
6 (due Wednesday May 26^{th}
– in class)  solution

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









