Open Course Space

Algorithmic Lower Bounds: Fun with Hardness Proofs

Massachusetts Institute of TechnologyUnited States6.890
Free, no sign-up neededFall 2014English
Go to course on MIT OpenCourseWare

6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs is a class taking a practical approach to proving problems can’t be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP). The class focuses on reductions and techniques for proving problems are computationally hard for a variety of complexity classes.

Description from MIT OpenCourseWare.

Where to take this course