Computability and Complexity Theory

4 credits

Survey of the theory of computation including Turing Machines, Churche's Thesis, computability, incompleteness, undecidability, complexity classes, problem reductions, Cook's theorem, NP-completeness, randomized computation, cryptography, parallel computation, and space complexity. Some emphasis placed on historical and philosophical aspects of the theory of computation.