CS 764 Course Description | SCS | UW

[Please remove <h1>]


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.