Computability and Computational Complexity

3 credits

This is a course in the theoretical foundations of computer science, centered around the theme of fundamental limits on computation. Topics include: Turing Machines, universal computation, undecidability of the halting problem, solvable and unsolvable algorithmic problems, recursive functions, Goedel's Incompleteness Theorem, time- and space-bounded computations, Cook's Theorem, NP-complete problems, problems solvable in polynomial space, randomized computation, application to cryptography, practical approaches to computationally intractable problems (such as SAT solvers), quantum computing, and Shor's Theorem.