CS 620 - Theory of Computation II

3 credits

Turing machines, the Church-Turing thesis, decidability, the halting problem, reducibility, recursive function theory, the recursion theorem, time and space complexity, classes P and NP, NP-completeness.

Prerequisites
CS 420 with a C or better or CS 520 with a C or better

View available class schedules