MATH 8850 ADVANCED AUTOMATA AND FORMAL LANGUAGES (3 credits)
A continuation of MATH 4660/MATH 8666/CSCI 4660/CSCI 8666. The course will be an introduction to computational complexity. Topics that will be covered include space and time complexities of Turing Machines, deterministic versus non-deterministic machines, NP-Complete problems, alternating Turing machines, and concepts of reducibility. (Cross-listed with CSCI 8850).
Prerequisite(s)/Corequisite(s): Not open to non-degree graduate students.