University of Vermont

2013-2014 Catalogue

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. Co-requisite: CS 124.
Credits: 3