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]

Lecture 1 Video [next]

[+] OPTIONAL — Introduction: class overview; complexity theory crash course (P, EXP, R, NP, coNP, PSPACE, hard, complete); fun hardness proofs: Mario, Rush Hour.

This first lecture gives a brief overview of the class, gives a crash course in most of what we'll need from complexity theory (in under an hour!), and tease two fun hardness proofs: Super Mario Bros. is NP-complete, and Rush Hour (the sliding block puzzle, not the movie) is PSPACE-complete. (All terms will be defined in lecture. We won't have time to play these games in lecture, though, so feel free to get some practice in. :-)) Don't worry — 6.5440 has lots of serious and fun hardness proofs.

Specifically, in the crash course we will define the complexity classes P, EXP(TIME), R, NP, coNP, PSPACE, and (less important) EXPSPACE, L, 2EXP, and 2EXPSPACE. We'll mention Savitch's Theorem (e.g., NPSPACE = PSPACE), the Time Hierarchy Theorem (e.g., P ≠ EXP ≠ 2EXP), and Space Hierarchy Theorem (L ≠ PSPACE ≠ EXPSPACE). Most importantly for this class, we'll define reductions, hardness, and completeness for these classes.

This week, we'll work on a bunch of solved/open/coding problems where (we think) we can reduce from 3-Partition or Numerical 3-Dimensional Matching (for strong NP-hardness) or at least Partition or Subset Sum (for weak NP-hardness). Of course, it's difficult to predict, so some problems may not be amenable — in which case we might consider them again in future weeks too.

Speaking of, feel free to work on last week's open problems too. There are some interesting remaining questions there based on the work so far, which I'll go over in class in our (probably daily) “progress report”.

I'll also go over a few tips for using Coauthor, which are also on the class website.

Finally, a reminder of the cadence of the class:

Coauthor posts are due Sunday (11:59pm Eastern)
Psets are due Monday at noon (PS1 already due, PS2 out now)
Watching video lectures is due by the first corresponding in-person class
Classes are Mondays & Wednesdays at 3-4:30+ and attendance is required (other than exceptions).