|[+] 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)
(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.
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.