Course Description
The fundamental limitations on mechanized computation. In the first part of the course, the emphasis is on possible versus impossible computations. Three classes of languages are considered: regular, context-free, and recursively enumerable. In the second part of the course the emphasis shifts to possible versus feasible computations.
Athena Title
AUTOMATA/FORMAL LAN
Prerequisite
CSCI 2670
Semester Course Offered
Not offered on a regular basis.
Grading System
A - F (Traditional)
Course Objectives
To master the fundamental methods and results of the theory of computing pertaining to decidability, time complexity, space complexity, and intractability.
Topical Outline
decidable languages the halting problem undecidable problems in language theory the Post correspondence problem mapping reducibility Turing reducibility time complexity and the classes P and NP NP-completeness and NP-complete problems space complexity and the class PSPACE PSPACE-completeness and PSPACE-complete problems log space complexity and the classes L and NL NL-completeness and NL-complete problems NL = co-NL space and time hierarchy theorems exponential space completeness relativized complexity classes circuit complexity