CSEP531: Computability and Complexity Theory
Catalog Description: 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.
Prerequisities: (none listed) Credits: 4.0Portions of the CSEP531 web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSEP531 Web: © 1993-2024, Department of Computer Science and Engineering, University of Washington. Administrative information on CSEP531 (authentication required).