[+] 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 NPcomplete, and Rush Hour
(the sliding block puzzle,
not the movie)
is PSPACEcomplete.
(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 3Partition or Numerical 3Dimensional Matching (for strong NPhardness) or at least Partition or Subset Sum (for weak NPhardness). 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:

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] 