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.

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