CMSC 281001: Introduction to
Complexity Theory
Class: Tue Thu : 09:00 AM10:20 AM in Ry 276
Tutorial:
Tue : 5  6 pm in Ry 255
Instructor: Ketan
Mulmuley Ryerson 165B
mulmuley@cs.uch...
Office Hour: Thursday 10:30  11:30

TA: Gokalp Demirci Ryerson 162C demirci@cs.uch...
Office Hour: Tuesday 12:30  1:30 @ Ryerson 162 (note slightly different time than announced in class)

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.
Other useful texts: (added by Gokalp)
Introduction to the Theory of Computation
by Michael Sipser.
Publisher: Course Technology; 3 edition, ISBN10: 113318779X, ISBN13: 9781133187790
Computational Complexity: A Modern Approach by
Sanjeev Arora and Boaz Barak.
Publisher: Cambridge University Press; 1 edition.ISBN10: 0521424267, ISBN13: 9780521424264
Computability: An Introduction to Recursive Function Theory by
Nigel Cutland.
Publisher: Cambridge University Press; 1 edition; 1 edition.ISBN10: 0521294657
ISBN13: 9780521294652

Assignments:

Will be posted here every Thursday, due before class (9am strict) the
following Thursday. You can submit your hw on chalk.uchicago.edu. Hw submission on chalk will close exactly at 9am. If you're not enrolled on class's chalk web page, send me an email.

Homework 1 due April, 6 (before class) Solutions


Homework 2 due April, 13 (before class) Solutions

Homework 3 due April, 20 (before class) Solutions

Homework 4 due April, 27 (before class) Solution guidelines

Homework 5 due May, 4 (before class) Solution guidelines

Homework 6 due May, 11 (before class) Solution guidelines

Homework 7 due May, 18 (before class) Solution guidelines

Midterm Solution guidelines

Homework 8 due May, 25 (before class) Solution guidelines

Homework 9 due June, 1

