Algorithmic Lower Bounds: Fun with Hardness Proofs
MIT's graduate course 6.890 teaches how to prove that computational problems cannot be solved efficiently, using reductions and hardness proof techniques rather than algorithm design. Lessons cover NP-hardness, PSPACE, and other complexity classes, building gadgets that reduce one problem to another and surveying the connections between combinatorial games and computation. Materials on MIT OpenCourseWare include lecture notes, problem sets, and readings covering topics like planarity gadgets, the complexity of puzzles and games, and reductions for scheduling and packing problems. The course assumes background in algorithms and complexity theory and is aimed at students who already know how to design efficient algorithms and now want to understand the limits of what is solvable in polynomial time. No video lectures are included, but the written materials are extensive enough to work through independently. Free to access, with no certificate offered.