CS3651 Computability Theory and Complexity

This course covers the concepts needed to argue the decidability and computational complexity of problems. Topics include recursive enumerability, undecidability, diagonalization, computational complexity classes, intractability, Turing reduction, and many-one reducibility. Basic techniques are presented for proving undecidability and for establishing a lower bound on the computational complexity of a problem.

Prerequisite

CS3101 and CS3150

Lecture Hours

3

Lab Hours

1

Quarter Offered

  • As Required