[Please remove <h1>]

---

Objectives

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

References to be determined.

Schedule

Three hours of lecture per week.

Outline

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.