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
MSC 11 6325
1 University of New Mexico
Albuquerque, NM 87131
Phone: (505) 277-8900
Fax: (505) 277-6809