Introduction to the Theory of Computation

CS 500 (3)

Covers basic topics in automata, computability and complexity theory, including: models of computation (finite automata, Turing machines and RAMs); regular sets and expressions; recursive, r.e., and non-r.e. sets and their basic closure properties; complexity classes; determinism vs. non-determinism with and without resource bounds; reductions and completeness; practice with NP- and P-completeness proofs; and the complexity of optimization and approximation problems.



Prerequisites / Corequisites


Course Search:




Keyword Search:

Office of the Registrar

MSC11 6325
1 University of New Mexico
Albuquerque, NM 87131

Phone: (505) 277-8900
Fax: (505) 277-6809