Graduate Theory of Computation

3 credits

Computability: Turing machines, universal computation, reducibility, undecidability, Rice's Theorem, Kolmogorov Complexity. Computational Complexity: Time complexity P, NP, and NP-complete problems. Cook-Levin Theorem. Space complexity - PSPACE and PSPACE-complete problems, Savitchs Theorem. Time and Space hierarchy theorems. Additional topics to be drawn from: Complexity of randomized computation, interactive proof systems, connections with cryptography, circuit complexity, quantum computing.Prerequisites: linear algebra; undergraduate discrete mathematics at the level of CSCI 2243 Logic & Computation.