Course: Introduction to Complexity Theory Classes: MWF 11:30-12:20 Ry 276 Instructor: Ketan Mulmuley Office Hour: Monday 4:15-5:15 Ry 165B Teaching Asst: Duru Turkoglu Tutorial/OH: Tuesday 6:00-7:30 Ry 256
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.
Title: Introduction to Automata Theory, Languages, and Computation, 3rd edition Authors: John Hopcroft, Rajeev Motwani, and Jeffrey Ullman Publisher: Addison-Wesley