CSC 524

Computational Complexity

Units: 1.5

Elements of the theory of computational complexity. Topics covered include: the distinction between tractable and intractable problems; definition of computational models and complexity classes; techniques for comparing the complexity of problems; the classes P and NP; completeness; auxiliary pushdown automata; alternating Turing machines; the polynomial time hierarchy; the classes Polynomial Space and Logarithm Space; probabilistic complexity classes; models of parallel computation; randomized computation.

Graduate course in the Computer Science program offered by the Faculty of Graduate Studies.

Fall 2017 Spring 2018 Summer 2018

Note that not all courses are offered in every term. If a course is not offered, the schedule page will alert you that "No classes were found that meet your search criteria."