CS 670 Advanced Theory of Computation

Computability and decidability; introduction to the theory of computational complexity; the classes sP and NP; NP-completeness; examples of some NP-complete problems; nondeterminism and parallel computation; proving the correctness of programs. Before enrolling, a student is expected to have taken CS 380 or an undergraduate theory of computation course.