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 2018 Spring 2019 Summer 2019

Summer timetable available: February 15. Fall and Spring timetables available: May 15.

Before these dates the class schedule will show "No classes were found that meet your search criteria". If this message is shown after these dates, the course is not scheduled for the selected term.