CMSC 28100-1: Introduction to Complexity Theory



Class: Tue Thu : 09:00 AM-10:20 AM in Ry 276

Tutorial: Tue : 5 - 6 pm in Ry 255


Instructor:
Ketan Mulmuley
Ryerson 165-B
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 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.


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, ISBN-10: 113318779X, ISBN-13: 978-1133187790

Computational Complexity: A Modern Approach
by Sanjeev Arora and Boaz Barak. Publisher: Cambridge University Press; 1 edition.ISBN-10: 0521424267, ISBN-13: 978-0521424264

Computability: An Introduction to Recursive Function Theory
by Nigel Cutland. Publisher: Cambridge University Press; 1 edition; 1 edition.ISBN-10: 0521294657 ISBN-13: 978-0521294652

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