- UNM
- >Catalogs
- >Catalog 2020-2021
- >Courses
- >Computer Science
- >Introduction to the Theory of Computation
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.
MSC11 6325
1 University of New Mexico
Albuquerque, NM 87131
(505) 277-8900
Phone: (505) 277-6809
Fax: