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.

Summer Fall Spring

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."