This course explores key challenges in computational complexity, focusing on hard computational problems and strategies for dealing with them. We begin with a recap of NP-hardness and polynomial-time reductions. From there, we delve into coping mechanisms with approximation algorithms. We will discuss a few techniques to design such algorithms and the limitations of approximability.
We will explore the complexity landscape further with topics like Ladner's Theorem, which sheds light on problems that are neither NP-complete nor in P, and complexity dichotomies that categorize problems into solvable and unsolvable groups under various frameworks. The course also covers #P-completeness and computational counting, examining problems whose complexity extends beyond decision problems to counting solutions.
