Aug 30, 2025  
2020-2021 Graduate Catalog 
    
2020-2021 Graduate Catalog [ARCHIVED CATALOG]

CSC 6010 - Theory of Computation II

Credits: 4
This continuation of CSC 3555, will explore the ideas of computability and complexity in more detail. The course will cover the topics of Turing Machines and other advanced models of computation (circuit model, oracle machines, alternating machines); complexity classes including: PSPACE, P, NP, coNP, L, P, RP, BPP, IP, AC, and AC0; and the polynomial hierarchy. Students will be expected to develop thorough proof-writing, reduction, and computational techniques, tested through regular quizzes and homework assignments.
Prerequisite(s): CSC 3555