Stony Brook University Logo Computer Science
CSE 540 Back to Graduate Courses

Course CSE540
Title Theory of Computation
Description

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.
Prerequisite

CSE 303

Credit Information 3 - credits
Course Goals  
Textbook(s) Introduction to the Theory of Computation, M. Sipser, 2nd or 3rd edition.
Recommended reading: Computational Complexity, S. Arora and B. Barak.
Course Webpage http://www.cs.stonybrook.edu/~cse540
[an error occurred while processing this directive]