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 (deterministic polynomial time); and NP (nondeterministic polynomial time); P and NP completeness; Auxiliary Pushdown Automata; Alternating Turing Machines; the polynomial time hierarchy; the classes Polynomial Space and Logarithm Space; probalistic complexity classes; models of parallel computation; can all problems in P be effectively parallelized? Randomized parallel 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."