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 administered by the Faculty of Graduate Studies.