20585 Introduction to the Theory of Computation and Complexity 1
Credits: 4 advanced credits in Computer Science
Prerequisites: Students must fulfill all English requirements and take bibliographic instruction in the Library.
Required: Algorithms, Automata Theory and Formal Languages
Recommended: Linear Algebra I, Probability for Computer Science Students
The course is based on Introduction to the Theory of Computation (2nd ed.), by M. Sipser (Thomson, 2006).
The course deals with questions concerning the abilities and limitations of computer computation. This is central to Computer Science theory and of great practical importance. The first part of the course addresses computability theory and discusses the question: “What is computable?” The second part of the course deals with complexity theory and discusses the question: “What can be computed efficiently?”
Topics: Part One: Computability Theory – Turing Machines; Decidable and undecidable problems, the undecidability of the halting problem; Reducibility, Rice’s theorem; Appendix – Advanced topics in computability theory: The recursion theorem, decidability of logical theories. Part Two: Complexity Theory – Time complexity, the classes P and NP; NP-completeness, the Cook-Levin theorem, polynomial time reducibility; Space complexity, the class PSPACE, the classes L and NL, NL-completeness; Hierarchy theorems; Advanced topics in complexity theory: approximation algorithms for NP-hard problems, probabilistic algorithms, the class BPP, primality testing.
1There is some overlap in the content of this and other courses. For details, see Overlapping Courses.