6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)

Prof. Erik Demaine     TAs: Sarah Eisenstat, Jayson Lynch


[Home] [Lectures] [Problem Sets] [Project] [Open Problems] [Piazza]

Lecture 1 Video     [next]

[+] Introduction: class overview; complexity theory crash course (P, EXP, R, NP, coNP, PSPACE, hard, complete); fun hardness proofs: Mario, Rush Hour. [Scribe Notes] [src]
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.

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]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.