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