CSC 485A - Theory of Computation

(3) This course is a study of relationships between automata and formal languages. Topics include: Foundations of automata theory, computability, and complexity theory, which problems can be solved by computational means using decidability versus undecidability, additional concepts related to the computational complexity of problems such as quantifiers and games, provably hard problems, relativized computation and oracles, probabilistic computation, interactive proof systems.

Prerequisites: CSC 240A, CSC 385A.