• Computability and Complexity

Catalog description

Investigate two big questions: How efficiently can computers solve problems? Are there problems that cannot be solved by computers at all? Computability theory: formal models of computation, Turing machines, universality, reductions, nondeterminism, and the Church – Turing thesis. Complexity theory: polynomial-time mapping reductions, NP-completeness, and the famous "P versus NP" problem. Prerequisites: COS 110 with a C- or higher or COS 111 with a C- or higher; MAT 248 with a C- or higher or Consent of instructor. Offered: Fall, even # years.