CMSC 28100-1 / MATH 28100-1: Introduction to Complexity Theory

Fall 2017

Class: Tuesdays and Thursdays, 12:30pm–1:50pm in Ryerson 251

Tutorial: Wednesdays, 6:30pm–7:30pm in Ryerson 277

Canvas course page for homework submissions: CMSC 28100 1 Intro Complexity Theory

Piazza course page for discussions: CMSC 28100-1 / MATH 28100-1

Ketan Mulmuley
Ryerson 165-B

Office Hour: Tuesdays, 2:00pm–3:00pm

Teaching Assistant:
Leonardo Nagami Coregliano
Theory Lounge – Ryerson 162

Office Hour: Wednesdays, 2:30pm–3:30pm


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 and Jeffrey Ullman, 1st edition, published by Addison Wesley, ISBN# 020102988X.
by John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, 3rd edition, published by Addison Wesley, ISBN# 0321462253.
(1st edition is better.)

Other useful texts:

Introduction to the Theory of Computation
by Michael Sipser. Publisher: Course Technology; 3rd edition. ISBN-10: 113318779X, ISBN-13: 978-1133187790.

Computational Complexity: A Modern Approach (draft can be found in the official website)
by Sanjeev Arora and Boaz Barak. Publisher: Cambridge University Press; 1st edition. ISBN-10: 0521424267, ISBN-13: 978-0521424264.

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


Will be posted here every Thursday, due next Thursday at noon, electronically on Canvas.
Solutions will be posted after due date.
LaTeX files can be found here.

Homework 1 due October, 5th (at noon) — Solution

Homework 2 due October, 12th (at noon) — Solution
A technical mistake was found in the original file. The link above is the correct version as of October 7th.

Homework 3 due October, 19th (at noon) — Solution

Homework 4 due October, 26th (at noon) — Solution

Homework 5 due November, 2nd (at noon) — Solution

Midterm solution

Homework 6 due November, 9th (at noon) — Solution

Homework 7 due November, 16th (at noon) — Solution

Homework 8 due November, 28th (Tuesday after Thanksgiving) (at noon) — Solution

Bonus Homework (optional), due November, 28th (Tuesday after Thanksgiving) (at noon) — Solution

Last modified: Nov 28, 2017 13:48, Central Standard Time