Course: Introduction to Complexity Theory Classes: MWF 11:30-12:20 Ry 276 Instructor: Ketan Mulmuley Office Hour: Wednesday 3:30-4:30 PM Ry 165B Teaching Asst: Ankan Saha Tutorial/OH: Monday 5-6 PM Ry 257
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