COM S 531: Theory of Computation
(3-0) Cr. 3.
Prereq: COM S 331
A systematic study of the fundamental models and analytical methods of theoretical computer science. Computability, the Church-Turing thesis, decidable and undecidable problems. Computational resources such as time, space, and nonuniformity. Complexity classes, computational intractability and completeness. Selected topics from randomness, algorithmic information theory, and logic.