Theory of Computation

Catalog description

In this course we will seek to understand what is and is not possible with modern daycomputers by using mathematical models to fine-grainly study various forms of computation. We will study languages, Turing machines, undecidability, the time complexity classes such as P, NP, NP-complete, space complexity classes such as L and NL, the Cook-Levin theorem, reductions, poly-time hierarchy, randomized algorithms and randomized complexity classes such as BPP, approximation algorithms and hardness of approximation. Lecture Hours: 3 Repeatability: May not be repeated for credit. Grade Mode: Normal, Audit Schedule Type (Primary): Lecture Click here for the Schedule of Classes.