The purpose of this course is to study the capabilities and limitations of computers, by formulating mathematically various models of idealized computers and establishing rigorously for these models what kinds of problems can and cannot be solved, as well as what kinds of problems can and cannot be solved with a reasonable amount of computing resources.

Topics include but not limited to:

• Computability theory: Turing machines, Church-Turing thesis, halting problem and unsolvability, universal Turing machine, introductory recursion theory;
• Complexity theory: complexity measures, time and space hierarchy, NP-complete problems, intractability;
• Advanced topics: probabilistic algorithms, interactive proofs, cryptography, computational game theory, quantum computation.

An introductory treatment of Turing machines would typically be part of an undergraduate course in the theory of computation, which is a prerequisite for this course. Though we shall cover this topic, the treatment will be fairly speedy, so as to leave enough time for complexity theory and advanced topics.

CSE540