[class poster]
[Games, Puzzles, and Computation book cover]

6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

Prof. Erik Demaine       TAs: Josh Brunner, Lily Chung, Jenny Diomidova

[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility]


Need to figure out when to give up the search for efficient algorithms?
Want to know why Tetris and Mario are computationally intractable?
Love seeing the connections between problems and how they can be transformed into each other?
Like solving puzzles that can turn into publishable papers?

This class takes a practical approach to proving problems can't be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP). We focus on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, we'll create many interesting gadgets, learn many hardness proof styles, explore the connection between games and computation, survey several important problems and complexity classes, and crush hopes and dreams (for fast optimal solutions).

The ability to show a problem is computationally hard is a valuable tool for any algorithms designer to have. Lower bounds can tell us when we need to turn to weaker goals or stronger models of computation, or to change the problem we're trying to solve. Trying to find lower bounds can help us see what makes a problem difficult or what patterns we might be able to exploit in an algorithm. The hardness perspective can help us understand what makes problems easy, or difficult to solve.

Inverted Lectures

This class features inverted lectures: most material is covered in video lectures recorded in 2014 (already watched by over 24,000 people), which you can conveniently play at faster speed than real time. In-class time will be focused on collaborative problem solving with your fellow students and the course staff. Particularly unusual is that the problems we'll solve in groups will include a choose-your-own-mix of problem-set style problems with known solutions, coding problems for those who love programming, and open research problems that no one knows the answer to, with the goal of publishing papers about whatever we discover. (Past offerings of this class have led to dozens of published papers.) You can work on whatever type of problem most interests you. To facilitate collaboration, we'll be using our open-source software platform called Coauthor, along with GitHub for (optional) coding.


This is an advanced class on algorithmic reduction. We will focus on techniques for proving problems are complete with respect to various complexity classes, not on the complexity theory itself. Here is a list of topics:

Readings and Resources

There is no textbook for this class, but there are two recommended books, and several other useful sources.
  1. Computational Intractability: A Guide to Algorithmic Lower Bounds: free 2024 book by Erik D. Demaine, William Gasarch, and Mohammad Hajiaghayi
  2. Games, Puzzles, & Computation: 2009 book by Robert A. Hearn and Erik D. Demaineavailable at MIT from CRCnetBASE
  3. Computational Complexity of Puzzles and Related Topics: 2022 survey paper by Ryuhei Uehara
  4. Computers and Intractability A Guide to the Theory of NP-Completeness: classic 1979 book by Michael R. Garey and David S. Johnson
  5. Johnson's followup NP-completeness Columns
  6. The Design of Approximation Algorithms by David Williamson and David Shmoys: chapter 16 is about inapproximability — ebook avalible from the MIT Library,     draft available for free download
  7. Limits to Parallel Computation: P-Completeness Theory by Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo — available for free download
  8. Complexity Zoo
  9. A compendium of NP optimization problems
  10. Erik's 6.046 notes proving some basic NP-hardness (3-Dimensional Matching, Subset Sum, 4-Partition)


Class Time: Mondays and Wednesdays at 3:00pm–4:30pm
Class Room: MIT room 32-082
First Class: Wednesday, September 6, 2023
Office Hours: by appointment (email staff)
Professor: Erik Demaine, 32-G680
TAs: Josh Brunner, 32-G580
Lily Chung, 32-G634
Jenny Diomidova, 32-G580
Staff Email: 65440-staff at csail.mit.edu
Units: 3-0-9
Prerequisites: 6.1210 or equivalent background in discrete mathematics and algorithms
Alternatively, permission from the instructor.
No background in computational complexity is required (though it doesn't hurt); all needed notions will be defined in this class.
Credit: AUS (Theory Track), AAGS (Theoretical CS Concentration)


We welcome both undergraduate and graduate students from all universities. Participation must be in person; there is no online component (beyond the freely available video lectures).

If you are interested in attending the class, for credit or as a listener, please do the following:

  1. Preregister for 6.S954 if you're from MIT/Harvard.
  2. Join the 65440-students mailing list.
  3. Sign up for an account on Coauthor.
  4. Sign up for an account on GitHub.com if you don't have one (this is different from github.mit.edu).
  5. Fill out this signup form.

Requirements & Grading

There are six components to the class, some of which are required:

required Watch all video lectures, measured by thumbs-upping completion questions on Coauthor (see your stats).
required Participate during all (or most) in-person classes (email 65440-staff about exceptions)
required Participate in class discussion, measured as coauthoring at least one nontrivial Coauthor post each week. See your statistics view to check for zero weeks.
(Example of a trivial post for a solved problem: "Use a reduction." Example of a nontrivial post for a solved problem: Describing the solution techniques you tried but failed. Deleted and unpublished posts do not count, but private posts do.)
choice Problem sets. Problem sets will be posted weekly.
choice Project write-up and presentation based on in-class work.

We're experimenting with a flexible grading scheme this semester:

  1. 20% for watching lectures [required]
  2. 40% for in-class participation [required]
  3. 50% for problem sets [optional]
  4. 50% for a project (or 25% for a small project) [optional]

The percentage weights sum to more than 100%. To compute your overall grade, we will reduce the percentage weight on your lowest-scoring problem set or project (whose weight isn't already zero) until the total weight reaches 100%. This lets you make up for lost points in one component by working more on the other components. In particular, three reasonable approaches to taking this class are to do problem sets and no project (20% + 40% + 50% = 110%, so still plenty of room to make up mistakes); one normal project and no problem sets (also 110%); or one small project and half the problem sets (also 110%). You can also do any combination, including multiple projects.

One additional rule is that you cannot pass the class without both watching most of the lectures and in-class participation most weeks (according to the fairly minimal requirements above), which is the meaning of "required".

Each component will be graded on a 100-point scale, then weighted as described above, then summed to produce your overall score. Your letter grade (A, B, etc.) will be assigned according to this score (where 90+ = A, 80+ = B, 70+ = C, 60+ = D, <60 = F). However, we reserve flexibility in assigning the annotation (+, −, or straight letter) according to other factors such as going above and beyond in participation or just scraping by.

Past and Future

The class is offered only occasionally. It was given in Spring 2019 (as 6.892) and Fall 2014 (as 6.890).