6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs (Spring 2019)

Prof. Erik Demaine       TAs: Jeffrey Bosboom, Jayson Lynch


[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.890 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.

In this class, we have a ton of solved and open problems related to Partition, 3-Partition, Edge Matching, and variants of Tetris. I'll also cover the notions of parsimonious and c-monious reductions, which (approximately) preserve the number of solutions, and why this is interesting (a look ahead to Lecture 10 that opens up a bunch of cool problems). And we'll briefly review the progress made on open problems last week. (We'll be doing such a "progress report" every week.)

Download Video: 360p, 720p

Handwritten notes, page 1/8[previous page][next page][PDF]

Handwritten notes, page 1/8[previous page][next page][PDF]

Slides, page 1/21[previous page][next page][PDF]

http://​courses.csail.mit.edu/​6.890/​fall14/​

Slides, page 1/21[previous page][next page][PDF]