University of Vermont

UVM Course Directory

Term: All Terms

Subject: Computer Science

Course Number: 125

CS 125 - QR: Computability& 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.