EECS 4115/5115, Fall 2025

Listed text: Sipser, Introduction to the Theory of Computation, 3rd ed. (2013), Part III.

References: Arora and Barak, Computational Complexity: A Modern Approach; Balcázar, Diaz and Gabarró, Structural Complexity I, 2nd ed.; Bovet and Crescenzi, Introduction to the Theory of Complexity; Du and Ko, Theory of Computational Complexity, 2nd ed.; Goldreich, Computational Complexity: A Conceptual Perspective; Homer and Selman, Computability and Complexity Theory, 2nd ed.; Immerman, Descriptive Complexity; Papadimitriou, Computational Complexity.

Original articles: Cook and Reckhow (1973), Time bounded random access machines; Hartmanis and Stearns (1965), On the computational complexity of algorithms.