sample frame from lecture video (L01)

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

Prof. Erik Demaine       TAs: Jeffrey Bosboom, Jayson Lynch

Lecture Videos and Classes [overview]

C01	Feb. 6	[+] Introduction: class overview; complexity theory crash course (P, EXP, R, NP, coNP, PSPACE, EXPTIME/SPACE, hard, complete); fun hardness proofs: Hamiltonicity, video games, 1 × n edge matching		[Erik's Notes]	[Slides]
	In our first class, I'll give an overview of the class and the format (which in future weeks involves watching video lectures), give a crash course in complexity theory and reductions, and show a few examples of Hamiltonicity-style reductions, proving hardness of a bunch of video games and of a puzzle called “1 × n edge matching” (a new result we proved in the last edition of this class). Then we'll all work in groups on related problems, some of which we know the answer to (pset-style) and some of which are unsolved problems in the field! (You can choose to work on any problems you like.) Please bring your laptop to class. Also, if you haven't already, please join the 6892-students mailing list, sign up for an account on Coauthor, and then fill out this signup form (even if you're just listening). Note that our Wednesday meeting time (7–9:30pm) is required attendance (for those taking for credit), but our Thursday meeting time (7–9pm) is optional. The main plan is to use Thursdays for extra time to work on open problems, but we may also use it for things like project ideas/discussions or helpful tutorials.
	L01	[+] OPTIONAL — Introduction: class overview; complexity theory crash course (P, EXP, R, NP, coNP, PSPACE, hard, complete); fun hardness proofs: Mario, Rush Hour.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	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.
C02	Feb. 13	[+] 3-partition. Parsimonious, c-monious, ASP, #P.		[Erik's Notes]
	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.)
	L02	[+] 3-partition I. 2-partition vs. 3-partition; variations (Subset Sum, Numerical 3-dimensional matching, 3DM, X3C); weakly vs. strongly NP-hard; pseudopolynomial vs. polynomial. Multiprocessor scheduling, rectangle packing, edge-matching puzzles, jigsaw puzzles, polyform packing puzzles, packing squares into a square.	Scribe Notes [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture introduces my favorite (and a generally lesser known) starting point for NP-hardness reductions, called 3-partition. This problem is particularly useful when you have a problem that involves adding up numbers, even when those numbers must be encoded in unary (a common feature of many puzzles). We'll discuss many variations of the problem: 2-partition: Partition integers into two sets of equal sum Subset Sum: Select integers to equal a target sum 3-partition: Partition n integers into n/3 triples of equal sum Numerical 3-dimensional matching: Integers are of three different types, and each triple must have all three types. 3-dimensional matching: A generalization to tripartite hypergraphs. Exact cover by 3-sets: A generalization to hypergraphs. 2-partition vs. 3-partition is an example of the weak vs. strong NP-hardness dichotomy, and on the algorithmic side, the pseudopolynomial vs. (weakly) polynomial dichotomy. We'll see weak and strong NP-hardness proofs, by reductions from 2-partition and 3-partition respectively, for two problems: multiprocessor scheduling packing rectangles into a rectangle Next we'll see a fun series of reductions between different puzzles, starting from 3-partition / rectangle packing to establish strong NP-hardness. edge-matching puzzles ("signed" like lizards, and "unsigned" like Eternity II) jigsaw puzzles polyomino packing puzzles (like Eternity) Finally, we'll see how to prove strong NP-hardness of packing squares into a square. This is a handy result that we'll use as the basis for another reduction next lecture.
	L03	[+] 3-partition II: edge-unfolding polyhedra, snake cube puzzle, disk packing, Clickomania, Tetris, 1-planarity, GeoLoop/Ivan's Hinge. 2-partition: ruler folding, simple map folding.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture includes a second (and final) bunch of strong NP-hardness reductions from 3-partition: Edge-unfolding polyhedra: A reduction from square packing (from L02). [Abel & Demaine 2011] Snake cube puzzle: Fold a chain of cubes with 90° bends at given locations into a larger cube. [Abel, Demaine, Demaine, Eisenstat, Lynch, Schardl 2013] Disk packing: Pack disks into a square (motivated by origami design). [Demaine, Fekete, Lang 2010] Clickomania: Delete monochromatic groups of size > 1 to erase everything. [Biedl, Demaine, Demaine, Fleischer, Jacobsen, Munro 2000] Tetris: Survive given piece sequence from given initial configuration. [Breukelaar, Demaine, Hohenberger, Hoogeboom, Kosters, Liben-Nowell 2004] 1-planarity: Drawing a graph so that each edge crosses at most one other edge. [Grigoriev, Bodlaender 2007] GeoLoop / Ivan's Hinge (piano-hinged dissections) [Abel, Demaine, Demaine, Horiyama, Uehara 2014] Plus we'll see a couple of weak NP-hardness reductions from 2-partition: Ruler folding: Fold a carpenter's ruler to fit inside a 1D box. [Hopcroft, Joseph, Whitesides 1985] Simple map folding: Fold a square piece of paper along one line at a time to achieve specified creases. [Arkin,Bender, Demaine, Demaine, Mitchell, Sethia, Skiena 2000]
C03	Feb. 20	[+] SAT			[Slides]
	We'll focus mainly on problem solving — we have many solved and open problems related to SAT. As usual, we'll also briefly review the progress on past open problems (and you're welcome to continue on those). I'll also briefly describe a software tool for drawing grid-based figures, called SVG Tiler, which we've used for drawing lots of hardness reductions.
	L04	[+] SAT. SAT, Circuit SAT, CNF SAT, 3SAT, 3SAT-4, Monotone 3SAT, 2SAT, Max 2SAT, Horn SAT, Dual-Horn SAT, DNF SAT, 1-in-3SAT / exact-1 3SAT, NAE 3SAT / Not-All-Equal 3SAT, Schaefer's Dichotomy Theorem, 2-colorable perfect matching. Pushing blocks: Push-1, Push-∗, PushPush, PushPushPush, Push-F, Push-X, Sokoban.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	Satisfiability, particularly 3SAT and its many variations, is the prototype NP-complete problem, forming the starting point for almost all NP-complete problems. This class gives an overview of all the important variations, particularly the NP-complete ones, but also some close cousins which are polynomially solvable (so no good for NP-completeness!). Then we'll see a few first examples of NP-hardness proofs based on 3SAT, centered around pushing block puzzles popular in many video games (and with practical applications to warehouse motion planning). After introducing a variety of different such puzzles, such as Sokoban, we'll prove NP-hard Push-∗ and Push-1 and PushPush-1 (first in 3D, then in 2D).
	L05	[+] SAT Reductions. Nintendo games (Super Mario World, glitches, Legend of Zelda, Metroid, Donkey Kong Country, Pokémon); Conway's Phutball (Philosopher's Football), mate-in-1, Checkers; cryptarithms (alphametics); origami flat-foldable crease patterns; vertex-disjoint paths (Numberlink)	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is filled with NP-hardness reductions from 3SAT, including: Nintendo games Super Mario Bros. (beyond Lecture 1) Legend of Zelda Metroid Donkey Kong Country Pokemon Conway's Phutball (Philosopher's Football), where mate-in-1 is NP-hard unlike Checkers Cryptarithm / alphametic puzzles Vertex-disjoint paths in a graph in a planar graph in a rectangle Origami crease patterns (flat foldability) Don't worry if you don't know any of the games — I will introduce each.
C04	Feb. 27	[+] Circuit and Planar SAT. Linked planar 3SAT.		[Erik's Notes]	[Slides]
	In this class, we'll talk about a new level of planar 3SAT called linked planar 3SAT. This problem is motivated by the type of planarity needed in e.g. the Super Mario Bros. NP-hardness proof: visit all the variables in some order to make choices, affect all the incident clauses, and then visit all the clauses in some order to check that they're all satisfied. Surprisingly, 3SAT remains NP-hard with this level of planarity, thanks to a paper by Pilz in 2018. Unfortunately, reducing from this problem is not quite as easy as it seems, as we need to take care about which sides the connections are on at the clause. We'll also have many solved and open problems related to planar SAT and circuit SAT and their many variations. Finally, we'll plan a bit for what to do with all the solutions to open problems we've been coming up with: research papers, final projects, etc.
	L06	[+] Circuit SAT. Dual-rail logic vs. binary logic; Akari/Light Up, Minesweeper (consistency and inference); planar Circuit SAT; Candy Crush / Bejeweled	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture starts with a distinction between two key SAT reduction styles: Dual-rail logic: variables + clauses (most proofs we've seen) Binary logic: wires + splitters + clauses (crease pattern proof) Circuit SAT: wires + splitters + universal gates Then we will see a few proofs in the Circuit SAT style: Akari / Light-Up (another Nikoli puzzle) Minesweeper consistency Minesweeper inference (which is actually coNP-complete) Candy Crush and Bejeweled (actually from 3SAT)
	L07	[+] Planar SAT. Planar 3SAT, planar monotone rectilinear 3SAT, planar positive 1-in-3SAT, planar NAE 3SAT (polynomial!), planar X3C, planar 3DM; planar vertex cover, planar (directed) Hamiltonian cycle, Shakashaka, flattening fixed-angle chains	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture introduces planar versions of 3SAT, in particular planar monotone rectilinear 3SAT and planar positive rectilinear 1-in-3SAT. But be careful: planar NAE 3SAT is polynomial. We will prove these versions of planar SAT are NP-hard. Then we'll reduce them to problems on planar graphs and in 2D geometry: Planar X3C (Exact 3-Set Cover) Planar 3DM (3-Dimensional Matching) Planar Vertex Cover Planar (Directed) Hamiltonian Cycle Shakashaka (another Nikoli puzzle) Flattening fixed-angle chains (at a high level)
C05	Mar. 6	[+] Hamiltonicity and other Graph Problems. Gadget framework (DAG case).		[Erik's Notes]	[Slides]
	This class, we'll have a bunch of solved and open problems related to Hamiltonicity and other graph problems such as graph covering/packing, including several more games and puzzles that we could analyze. We'll also cover a relevant piece of our new general “theory of gadgets” for puzzles with an agent/robot, and mention a useful new graph problem called “tree-residue vertex-breaking”.
	L08	[+] Hamiltonicity. Icosian game, planar directed max-degree-3, planar bipartite max-degree-3, max-degree-3 square grid graphs, triangle grid graphs, hex grid graphs, unit orthogonal segment intersection graphs. Euclidean degree-3 MST, Settlers of Catan mate-in-0, Slitherlink, Hashiwokakero. Milling, lawn mowing, 3D printing, minimum turns.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about Hamiltonicity (paths/cycles that visit every vertex exactly once). In particular, we'll see a very special and useful case that is NP-hard: grid graphs, defined by a set of points on a grid, with edges exactly when two points have unit distance. This version is hard for square, triangular, and hexagonal grids. We'll prove this and see how to reduce to other fun problems like optimally mowing your lawn, 3D printing, Settlers of Catan, and Nikoli puzzles Slitherlink and Hashiwokakero.
	L09	[+] Graph Problems. Vertex Cover: planar max-degree-3; exact vertex cover (polynomial), edge cover (polynomial), connected vertex cover, rectilinear Steiner tree. Vertex Coloring: planar max-degree-4 3-coloring, max-degree-3 3-coloring (polynomial), Push-1X, Push-1G (gravity). Graph Orientation: 1-in-3, 2-in-3, 0-or-3 vertices; packing trominoes. Graph Layout: Bandwidth, minimum linear arrangement, cutwidth, vertex separation, sum cut, edge bisection, vertex bisection; betweenness; bipartite crossing number, crossing number, Rubik's Cube.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is our last about straight-up NP-hardness. We've already seen the main techniques for such proofs, but there are a few other techniques that get used now and then. We will see three: Vertex cover, in particular planar vertex cover and planar connected vertex cover Vertex coloring, in particular planar max-degree-4 3-coloring Graph orientation, about assigning edge directions to satisfy vertex constraints. In particular, we will use these techniques to prove hardness of Rectilinear Steiner tree Pushing-block puzzles Push-1X and Push-1G (gravity) Crossing number A version of Rubik's Cube (just a rough sketch)
C06	Mar. 13	[+] Counting and Games. Polynomial Hierarchy (Σk and Πk). Unbounded 1-player general theory of gadgets.		[Erik's Notes]	[Slides]
	In this class, we'll tackle several problems related to #P/ASP and PSPACE-complete one-player games. We'll also cover the corresponding unbounded one-player general theory of gadgets, as well as a little bit about the Polynomial Hierarchy (Σk and Πk, between NP and PSPACE).
	L10	[+] #P and ASP. NP search problem, # problems, #P, parsimonious and c-monious reductions, SAT problems, Shakashaka, Hamiltonicity, Slitherlink, permanent, counting bipartite (perfect/maximal) matchings, counting minimal vertex covers, positive #2SAT. ASP (Another Solution Problem).	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about counting solutions, instead of just finding one. Given an NP problem and a notion of certificates for that problem, the counting version of the problem is to determine the number of valid certificates for a given instance. Analogous to NP, we get a class #P. In the world of Karp-style reductions, we get the notion of parsimonious (and “c-monious”, a term I made up) reductions that preserve the number of solutions (possibly with a uniform scale factor c). Many #P-hardness reductions are obtained this way. More generally, though, #P-hardness is defined relative to Cook-style multicall reductions. After reviewing some old proofs and whether they are parsimonious, we'll prove a bunch of problems #P-complete: Permanent of a matrix 0/1 permanent = counting perfect matchings in planar graphs #2SAT Hamiltonicity Nikoli puzzles Shakashaka and Slitherlink We'll also discuss the related notion of ASP (Another Solution Problem) and ASP-completeness. This area is motivated by many puzzles (such as Nikoli puzzles) which are supposed to be designed to have unique solutions. How can we tell whether the solution is unique, or equivalently, whether the puzzle has a second solution? Here we need our reductions to preserve solution uniqueness, a weaker condition than parsimony (but not c-mony).
	L11	[+] NP & PSPACE Video Games. Base PSPACE-complete problems: QSAT, Schaefer, planar Q3SAT, planar 1-in-3 Q3SAT. Viglietta metatheorems: location traversal, single-use paths, tokens, toll roads, pressure plates, buttons, doors. Applications to video games: Pac Man, FPSs (Doom, Quake, Heretic, Hexen), RPGs (Eye of the Beholder), adventure games (SCUMM), platformers (Prince of Persia, Sonic the Hedgehog, The Lost Vikings, Tomb Raider, Zelda II, Donkey Kong Country 1, 2, 3, Super Mario Bros., Lemmings)	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	Back to fun hardness of video games! We'll prove a bunch of “metatheorems”: video games with a few basic features are NP-hard or PSPACE-hard. Then we'll apply these metatheorems to prove NP-hardness of Boulderdash, Lode Runner, Zelda II, and Pac Man; and PSPACE-hardness of FPSs (e.g. Doom), RPGs (e.g. Eye of the Beholder), adventure games (e.g. SCUMM), Prince of Persia, Legend of Zelda: A Link to the Past, Donkey Kong Country 1, 2, and 3, and Lemmings.
C07	Mar. 20	[+] Constraint Logic. Mate-in-k. Reals and ∃R. Bounded 2-player general theory of gadgets.		[Erik's Notes]	[Slides]
	In this week's class, we'll briefly revisit Σk from the perspective of 2-player games (mate-in-k), mention the real-valued analogs to NP/PSPACE, and cover the bounded 2-player case of the general theory of gadgets.
	L12	[+] Nondeterministic Constraint Logic (NCL). Constraint graph, AND/SPLIT vertex, OR vertex, protected OR vertex, CHOICE vertex, red-blue conversion, wire terminators, crossovers, grid graphs. Constraint Graph Satisfaction is NP-complete, NCL is PSPACE-complete. Reconfiguration 3SAT, sliding-block puzzles, sliding tokens, Rush Hour, hinged dissection, Sokoban, Push-2F, rolling-block mazes, plank puzzles (River Crossing), dynamic map labeling, partial searchlight scheduling.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about Constraint Logic. We saw the basic model in Lecture 1 to prove Rush Hour is PSPACE-complete. Now we'll see the details of how Nondeterministic Constraint Logic (NCL) works, why it's PSPACE-complete, and how we can reduce to a very small gadget set: planar graphs with just AND and protected OR vertices. Then we'll apply NCL to prove PSPACE-completeness proofs for several different puzzles and problems: Reconfiguration 3SAT Sliding-block puzzles Sliding tokens Rush Hour Hinged dissection reconfiguration Sokoban Push-2F Rolling-block mazes Plank puzzles / River Crossing Dynamic map labeling Partial searchlight scheduling
	L13	[+] 0- and 2-player games. 0-player games: Conway's Game of Life is undecidable, Deterministic Constraint Logic (DCL) is PSPACE-complete. Bounded 2-player games are PSPACE-complete: impartial/partizan game/avoid/seek SAT, Kayles, Geography, Reversi/Othello, bounded 2-player Constraint Logic (Bounded 2CL).	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	We've proved hardness of a lot of puzzles, which can be viewed as 1-player games — the player represents the nondeterminism in move choices. This lecture is about games involving fewer or more players. Zero-player games are essentially simulations, like a regular computer. The prototypical example here is Conway's Game of Life, which is PSPACE-complete or undecidable depending on whether you bound the board. A more modern example is Deterministic Constraint Logic, a version of constraint logic where edge-reversal order is deterministically defined (but many edges reverse in parallel), which is still PSPACE-complete. In multiplayer games, we want to know whether a player (say, the first) has a winning strategy. In the worst case, all other players collude as a single entity, so the game reduces to two players. Thus we obtain 2-player games. We'll see many typical starting points for proving hardness of 2-player games, from QSAT itself to impartial/partizan game/seek/avoid SAT (from another amazing Schaefer paper). PSPACE-hard 2-player graph games include Kayles (essentially 2-player independent set), Geography (essentially 2-player longest path), Reversi/Othello, and bounded 2-player Constraint Logic (Bounded 2CL).
C08	Apr. 3	[+] Higher Games / Constraint Logic.		[Erik's Notes]	[Slides]
	We'll have a slew of problems related to Constraint Logic, 2-player games, stochastic games, and other unusual types of games. We'll also briefly cover the last known results in the general theory of gadgets.
	L14	[+] More Games. PSPACE-complete bounded 2-player games: Amazons, Konane, Cross Purposes. PSPACE-complete bounded 1-player stochastic games: SSAT. EXPTIME-complete unbounded 2-player games: formula games (G1, G2, G3, G4, G6), Peek, graph games (Ham, Block), Checkers, Chess, Go with Japanese ko rule, planar unbounded 2CL. APSPACE = EXPTIME. EXPSPACE-complete no-repeat unbounded 2-player games. 2EXPTIME-complete conditional no-repeat unbounded 2-player games. 2EXPTIME-complete private-information unbounded 2-player games. EXPSPACE-complete blind unbounded 2-player games.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	In this class, we'll see a few examples of real bounded games proved PSPACE-complete via Constraint Logic: Amazons, Konane, and Cross Purposes. Then we'll work our way up the game hierarchy: unbounded two-player games are EXPTIME-complete (including Chess, Checkers, and Japanese Go); with a “no repeat” rule they become EXPSPACE-complete (conjectured to include USA/Chinese Go); and with a “no recent repeat” rule they become 2EXPTIME-complete. Impartial information among the players similarly increases the complexity of unbounded two-player games, and furthermore distinguishes two-player games from team games with more than two players. I'll also mention some results that random (stochastic) players, such as rolling the dice, can be just as adversarial as regular (optimal) players — so-called “Games Against Nature”.
	L15	[+] Undecidability & P-completeness. Bounded team games with private information are NEXPTIME-complete: bounded Team Private Constraint Logic (TPCL). Unbounded team games with private information are undecidable: Team Computation Game, Team Formula Game, TPCL. P-completeness: NC, P-complete, machine simulation, Circuit Value Problem, SAM2CVP, bounded DCL, lexically first maximal independent set (greedy).	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture completes our coverage of games, explaining how it can be undecidable to determine winning strategies in games with bounded “resources”, when those games have private information and teams. Essentially, we can exploit the player's “heads” to store an arbitrarily large amount of information, and perform an arbitrarily complex computation in a long sequence of moves, even though the game's memory is itself small. In particular, the natural version of Constraint Logic is undecidable. (If the game has polynomially bounded length, however, the game is “only” NEXPTIME-complete.) This lecture also covers the notion of P-completeness (a frequent request from the survey), which is about the limits of parallel computation. P-complete problems are likely not in NC, meaning that they cannot be solved in polylogarithmic time even given a polynomial number of processors/gates. Constraint logic can be adapted here too, with bounded DCL. One detail here is that reductions need to be parallel algorithms, but this is pretty easy in gadget-based reductions.
C09	Apr. 10	[+] Inapproximability. 1 × n edge matching has no PTAS, gap reductions.			[Slides]
	We'll work on several problems related to approximation algorithms, the theme of this week. We'll kick things off by covering a result (from 6.890 in 2014) that 1 × n edge matching has no PTAS (according to two natural objective functions), which highlights the power of gap reductions.
	L16	[+] Inapproximability Intro. NP optimization problem, approximation, PTAS, APX, Log-APX, Poly-APX, PTAS-reduction, AP-reduction, strict-reduction, A-reduction, L-reduction, APX-hard. Max E3SAT-E5, Max 3SAT-3, independent set, vertex cover, dominating set.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture begins a series on inapproximability — proving the impossibility of approximation algorithms. I'll give a brief overview of most of the typical approximation factor upper and lower bounds in the world of graph algorithms. Then we'll introduce a bunch of general concepts, including new complexity classes (NPO, PTAS, APX, Log-APX, etc.) and stronger notions of reductions that preserve approximability (PTAS-, AP-, strict-, A-, and L-reductions). Finally, we'll prove APX-hardness for a bunch of APX-complete problems: Max 3SAT-3 Independent set Vertex cover Dominating set
	L17	[+] Inapproximability Examples. Max 2SAT, max NAE 3SAT, max cut, max/min CSP/ones characterization, max independent set, max 3DM-E2, max edge matching puzzles. APX-intermediate. Log-APX-complete: set cover, dominating set, token reconfiguration. Poly-APX-complete: independent set, clique. Exp-APX-complete: nonmetric Traveling salesman. NPO PB-complete: independent dominating set, longest induced path. NPO-complete: weighted SAT, 0-1 linear programming,	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture beings with a bunch more L-reductions to prove various problems APX-complete: Max 2SAT Max NAE 3SAT Max cut (max positive 1-in-2SAT) Max 3-dimensional matching Edge matching puzzles (maximize number of matches) More generally, we'll see a powerful characterization theorem of when minimizing or maximizing the number of satisfied clauses or number of true variables is approximable or inapproximable according to the structure of those clauses (in the spirit of Schaefer's Dichotomy Theorem). Next we'll also see some Log-APX-hardness, L-reducing from set cover to Dominating set Token reconfiguration puzzles I'll also briefly mention the higher end of the approximation spectrum: Poly-APX-complete: max independent set and clique Exp-APX-complete: nonmetric traveling salesman NPO PB-complete: longest induced path, longest path with forbidden pairs, minimum independent dominating set, shortest computation NPO-complete: max/min weighted SAT — find a satisfying assignment that maximizes/minimizes the sum of weights of true variables — and max/min 0-1 linear programming
	L18	[+] Gap Inapproximability. Gap problem, gap-producing and gap-preserving reductions, PCP theorem, max E3-X(N)OR-SAT, max E3SAT, Label Cover (Max-Rep and Min-Rep), directed Steiner forest, node-weighted Steiner tree, Unique Games Conjecture.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about gap problems: distinguishing between good and bad solutions, with a big gap in between those two notions. This perspective is particularly nice because we can turn NP-hardness of a decision problem into NP-hardness of approximation. It also often leads to tighter bounds on approximability. For example, we'll see a reduction that gives an optimal 7/8-inapproximability for Max E3SAT. A big tool here is the PCP (Probabilistically Checkable Proofs) theorem, which won a Gödel Prize in 2001. We'll see how gap problem hardness naturally leads to probabilistically checkable proofs and vice versa. Then we'll see the core PCP lower bound theorems, a problem called label cover (MinRep and MaxRep). Finally, we'll cover the Unique Games Conjecture, which (if true) leads to further improved inapproximability constants.
C10	Apr. 17	[+] Parameterized Complexity
	In this class, we'll have a bunch of problems related to parameterized complexity work on. No new lecture material.
	L19	[+] Parameterized Complexity I: W Hierarchy. Parameter, parameterized problem, XP, fixed-parameter tractable (FPT), Vertex Cover, EPTAS, parameterized reduction. W[1]: k-step nondeterministic Turing machine, Independent Set, clique in regular graphs, partial vertex cover, multicolored clique, shortest common supersequence, Flood-It on trees. W[2]: dominating set, set cover. W hierarchy: depth, weft, Weighted Circuit SAT, W[P], W[t], W[*], W[1], W[2], W[SAT].	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture begins our analysis of decision problems from a parameterized perspective, where we consider the dependence on an arbitrary parameter k in addition the problem size n. The algorithmic goal is to confine the exponential dependence to the parameter k instead of the problem size n. In this way, we get a deeper understanding of when the exponential time is reasonable (i.e. when k is small). More precisely, a problem is fixed-parameter tractable (FPT) if we can solve it in f(k) nO(1), for any function f(k), and constant O(1) independent of k. By contrast, a time bound of nf(k) is considered bad (but it has its own complexity class, XP). We'll introduce classes W[1] and W[2] conjectured to be distinct from FPT, by analogy to P ≠ NP. Then we'll see several problems that are complete in this classes, under a new reduction type called parameterized reduction. Specifically, k-step nondeterministic Turing machine is the canonical hard problem for W[1]. We'll prove that it's equivalent to Independent Set, and use that to prove W[1]-hardness of clique/independent set in regular graphs, partial vertex cover, and a useful base problem called multicolored independent set. We'll also see a reduction from the W[1]-hard problem shortest common supersequence to a puzzle game called Flood-It on trees. For W[2], the typical starting problems are Dominating Set and Set Cover. We'll show that these problems are at least as hard as W[1] by a reduction from multicolored independent set. Finally, we'll define the general W hierarchy in terms of the depth and weft of circuits and a problem called Weighted Circuit SAT (which could also be called Circuit k-Ones).
	L20	[+] Parameterized Complexity II: ETH & Planar. Exponential Time Hypothesis (ETH), strong ETH, 3-coloring, reduction size blowup, vertex cover, dominating set, Hamiltonicity, independent set, clique, planar 3SAT, planar graph problems, parameterized consequences of ETH, parameter blowup. Planar problems: Grid Tiling, list coloring, grid tiling with ≤, scattered set, independent set in unit-disk graphs.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about strong lower bounds on running time that are possible by assuming the Exponential Time Hypothesis: there is no 2o(n) algorithm to solve n-variable 3SAT. This conjecture is a stronger form of P ≠ NP, and it lets us keep track of “problem size blow-up”, something we've ignored before in our NP-hardness reductions. Many of the reductions we've seen, such as 3-coloring, vertex cover, dominating set, Hamiltonicity, and Independent Set/Clique have linear blow-up, so we get 2o(n) lower bounds. On the other hand, planar versions of these problems (except Clique) have quadratic blow up because of the crossover gadgets, so we get 2o(√n) lower bounds. In parameterized complexity, we get a particularly strong form of FPT ≠ W[1]: there is no f(k) no(k) algorithm for Clique/Independent Set, for any computable function f. In particular, there's no f(k) nO(1) (FPT) algorithm. By keeping track of the parameter blowup in our parameterized reductions, we can prove similar bounds for other problems, e.g. multicolored Clique/Independent Set, Dominating Set, Set Cover, and Partial Vertex Cover. Finally, we'll cover a useful base problem, called Grid Tiling, for proving W[1]-hardness of problems on planar graphs or in 2D. Specifically, we'll use Grid Tiling to prove Scattered Set is W[1]-hard in planar graphs, and that Independent Set is W[1]-hard in in unit-disk graphs. These results also imply that these problems have no EPTAS.
C11	Apr. 24	[+] Free-For-All
	This class, we don't have any assigned lecture videos (or new lecture material), but we'll still bring a bunch of fun problems in complexity.
C12	May 1	[+] Free-For-All		Erik's Notes
	Alas, this week's class will be the last one in which we solve problems! We have a bunch more new open problems, including a lot of fun video games. (No solved problems this week; if you don't want to work on open problems, work on your project!) In addition, I'll present the 1-page slide summaries of the presentations to come in the final two class sessions.
C13	May 8	[+] Student Presentations I (room 32-141)
C14	May 15	[+] Student Presentations II (room 32-141)
	L21	[+] OPTIONAL — 3SUM & APSP. k-SUM upper and lower bounds, reductions. Distinct 3SUM, 3SUM′, GeomBase, 3 points on a line, point on 3 lines, Separator, Strips cover box, Triangles cover triangle, Hole in union, Triangle measure, Point covering, Visibility between segments, Visible triangle, Planar motion planning, 3D motion planning, fixed-angle chains. Nonquadratic lower bounds for triangle finding. Conjectured cubic graph problems: diameter, all-pairs shortest paths, negative triangle, radius, median.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about hardness of problems that can be solved in polynomial time but where that polynomial seems to be substantially superlinear. Our focus will be on 3SUM (given n integers, do any 3 sum to zero?) which is conjectured to require roughly Θ(n2) time to solve. It has been the basis for many “3SUM-hardness” reductions, so if any of the problems can be solved in O(n2 − ε) time, then so can 3SUM. In class, we'll prove many problems 3SUM-hard, including a lot of computational geometry (where 3SUM originally comes from). We'll also talk about the generalization k-SUM, which has fairly strong lower bounds assuming ETH, and the conjectured-cubic graph problems all-pairs shortest paths and diameter.
	L22	[+] OPTIONAL — PPAD (guest lecture by Constantinos Daskalakis). Economic games, Nash equilibrium, Nash's Theorem, Brouwer's Fixed-Point Theorem, Sperner's Lemma, proofs and computational versions. Total search problems (TFNP), directed parity argument, End of the Line, PPAD, Arithmetic Circuit SAT.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is the first of two guest lectures by Prof. Constantinos Daskalakis about the class PPAD which is intricately related to economic game theory (and a cool idea more generally). Costis is the expert in this area — his PhD thesis, for example, proved that finding Nash equilibria is PPAD-complete. Specifically, this lecture illustrates beautiful connections (reductions) between Nash's Theorem in economic game theory, Brouwer's Fixed-Point Theorem in topology, and Sperner's Lemma in graph theory. These problems are all PPAD-complete, meaning that they are the hardest search problems that have guaranteed solutions via “directed parity arguments” (formally, a problem called End of the Line). To prove PPAD-hardness (in the next lecture), we introduce an analog of Circuit SAT called Arithmetic Circuit SAT.
	L23	[+] OPTIONAL — PPAD Reductions (guest lecture by Constantinos Daskalakis). PPAD-completeness of Nash: graphical games, polymatrix games, 2-player games. PPA (Handshaking Lemma), PLS (sinks exist), PPP (pigeonhole principle).	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This class is Costis Daskalakis's second of two guest lectures. We'll focus on examples of PPAD-completeness reductions, from Arithmetic Circuit SAT to Nash equilibria in a few different settings—ultimately two-player games. Not covered but in the slides are other examples of PPAD-hardness reductions. Finally we'll hear about other classes related to PPAD, based on other styles of proofs of existence of solutions. PPA is based on the fact that, if a graph has a node of odd degree, then it must have another (which follows from the Handshaking Lemma). PLS is based on the fact that every directed acyclic graph has a sink node. PPP is based on the Pigeonhole Principle: any mapping from a set to a set of a smaller size has a collision.

Credits