CS 125 - Computability and Complexity

Formal languages and expressiveness. Turing completeness and Church's Thesis. Decidability and tractability. Complexity classes and theory of NP completeness. Prerequisites: CS 064 or MATH 052. Recommended co-requisite: CS 124.

Credits: 3