CS-850 — Advanced Theory of Computation

Course Description

This course examines the theoretical foundations of computation at a graduate level, building on undergraduate automata theory to study computability, decidability, and computational complexity in depth. Topics include advanced models of computation, the Church-Turing thesis, the halting problem and undecidability, complexity classes such as P, NP, and PSPACE, NP-completeness and reduction techniques, and an introduction to advanced topics such as randomized and approximation complexity.

The course emphasizes rigorous proof technique and mathematical maturity, preparing students to engage with research-level questions in theoretical computer science and to apply complexity-theoretic reasoning when evaluating the tractability of problems in their own research.

Course Outcomes / Objectives

Formally define and reason about advanced models of computation, including Turing machines and their variants.
Prove decidability and undecidability results using reduction and diagonalization techniques.
Classify problems by complexity class (P, NP, PSPACE, etc.) and reason about the relationships between them.
Prove NP-completeness of a problem via polynomial-time reduction from a known NP-complete problem.
Critically evaluate the tractability of computational problems arising in research and practice.

Text Books

Introduction to the Theory of Computation (3rd ed.) — Michael Sipser — primary textbook
Computational Complexity: A Modern Approach — Sanjeev Arora & Boaz Barak — supplementary reference