CS 764 Computational Complexity


To give the student further exposure to the classification of problems based on their computational requirements, and to mathematical tools designed to explore the structural consequences of such classifications.

Students are expected to have basic knowledge of complexity theory (P, NP, NP-completeness).


References to be determined.


Three hours of lecture per week.


Structural Complexity (18 hrs)

Relativization. Structure of NP. Alternation and the polynomial-time hierarchy. Interactive proof systems. Provably intractable problems. Feasible parallel computations, Boolean circuits, and the class NC.

Parameterized Complexity (9 hrs)

Fixed-parameter tractability. Kernelization and bounded search trees. Relationship to optimization problems and approximation schemes. Parameterized reducibility and W[1]-completeness. The W-hierarchy.

Kolmogorov Complexity (9 hrs)

Randomness and incompressibility. Robustness. Algorithmic complexity and algorithmic prefix complexity. Applications to computational complexity.

Campaign Waterloo

David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293
Fax: 519-885-1208

Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics

Valid HTML 4.01!Valid CSS! Last modified: Friday, 01-Jun-2012 11:00:32 EDT