Computational Complexity

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. Topics include relativization, alternation, provably intractable problems, feasible parallel computation; fixed-parameter tractability and the W-hierarchy; Kolmogorov complexity, including algorithmic and algorithmic prefix complexity and their applications.