|C01||Sep. 6||[+] Introduction: class overview; complexity theory crash course (P, EXP, R, NP, coNP, PSPACE, EXPTIME/SPACE, hard, complete); fun hardness proofs: Hamiltonicity in grid graphs, The Witness video game||[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; show a useful Hamiltonicity problem (in grid graphs) to reduce from; and prove hardness of a bunch of puzzle types in the video game The Witness, which are from a paper “Who Witnesses The Witness?” that grew out of the open problem session from a past version 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 65440-students mailing list, sign up for an account on Coauthor, and then fill out this signup form (even if you're just listening).
|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)
(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.
|C02||Sep. 11 & 13||[+] 3-partition. Coauthor tips.||[Erik's Notes]|
This week, we'll work on a bunch of solved/open/coding problems where (we think) we can reduce from 3-Partition or Numerical 3-Dimensional Matching (for strong NP-hardness) or at least Partition or Subset Sum (for weak NP-hardness). 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:
|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 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:
Next we'll see a fun series of reductions between different puzzles, starting from 3-partition / rectangle packing to establish strong NP-hardness.
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.
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:
Plus we'll see a couple of weak NP-hardness reductions from 2-partition:
|C03||Sep. 18 & 20||[+] SAT I. Polymorphism view of Schaefer's Dichotomy, nonbinary SAT/CSP dichotomy, planar dichotomy, symmetric dichotomy, S-in-kSAT||[Erik's Notes]|
This week is our first about SAT — in particular the NP-hard versions 3SAT, 1-in-3SAT, NAE 3SAT, planar 3SAT, and planar 1-in-3SAT. I'll kick us off with a modern “polymorphism” view of Schaefer's Dichotomy characterizing which versions of SAT are hard, along with extensions to nonbinary variables and restrictions to planar formulas.
Then we have a suite of new open, solved, and coding problems about variations of SAT and pushing blocks.
|L04||[+] SAT. SAT, Circuit SAT, CNF SAT, 3SAT, 3SAT-3, 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. Conway's Phutball (Philosopher's Football), mate-in-1, Checkers.||[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 cover some examples of NP-hardness proofs based on 3SAT. First we'll look at 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). Finally, we'll cover Conway's Phutball (Philosopher's Football), where mate-in-1 is NP-hard, unlike Checkers where mate-in-1 is polynomial.
|L05||[+] 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]|
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:
|C04||Sep. 25 & 27||[+] SAT II|
|L06||[+] Linked Planar SAT. Linked, sided, monotone, planar 3SAT-3, interlinked; opening doors with 2 buttons, closing doors, Mario, Pokémon, Zelda, (Push)Push-1(X), Push-1G, Pull?-1FG.||[Erik's Notes]||[Slides]||[Video]|
This lecture introduces Linked Planar 3SAT. Linked planar 3SAT is very useful for reductions for Mario-style games where an agent needs to traverse variable gadgets followed by clause gadgets without needing a crossover.
In Linked Planar SAT, we have planar bipartite graph of variables and clauses, and also have cycle containing all of the variables followed by all of the clauses. We'll show this is NP-complete.
We'll also introduce the door opening and door closing as an application of linked planar 3SAT, and use it to simply NP-hardness proofs of Mario, Zelda, Pokémon, and other games.
|L07||[+] 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:
|C05||Oct. 2 & 4||[+] Hamiltonicity and other Graph Problems.|
|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.
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).
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:
|C06||Oct. 11, 16, 18||[+] Motion-Planning Games.|
|L10||[+] 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.
|L11||[+] Motion-Planning Gadgets.||[Erik's Notes]||[Slides]||[Video]|
Needs a description
|C07||Oct. 23 & 25||[+] Constraint Logic.|
|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:
|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||Oct. 30 & Nov. 1||[+] Higher Games / Constraint Logic.|
|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||Nov. 6 & 8||[+] Beyond Decision Problems.|
|L16||[+] #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:
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).
|L17||[+] 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:
|C10||Nov. 13 & 15||[+] Inapproximability|
|L18||[+] 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:
|L19||[+] 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.
|C11||Nov. 20 & 22||[+] Parameterized Complexity|
|L20||[+] Parameterized Complexity I: W Hierarchy. Parameter, parameterized problem, XP, fixed-parameter tractable (FPT), Vertex Cover, EPTAS, parameterized reduction. W: k-step nondeterministic Turing machine, Independent Set, clique in regular graphs, partial vertex cover, multicolored clique, shortest common supersequence, Flood-It on trees. W: dominating set, set cover. W hierarchy: depth, weft, Weighted Circuit SAT, W[P], W[t], W[*], W, W, 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 and W 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. We'll prove that it's equivalent to Independent Set, and use that to prove W-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-hard problem shortest common supersequence to a puzzle game called Flood-It on trees. For W, the typical starting problems are Dominating Set and Set Cover. We'll show that these problems are at least as hard as W 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).
|L21||[+] 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
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:
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-hardness of problems on planar graphs or in 2D. Specifically, we'll
use Grid Tiling to prove Scattered Set is W-hard in planar graphs,
and that Independent Set is W-hard in in unit-disk graphs.
These results also imply that these problems have no EPTAS.
In parameterized complexity, we get a particularly strong form of FPT ≠ W: 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-hardness of problems on planar graphs or in 2D. Specifically, we'll use Grid Tiling to prove Scattered Set is W-hard in planar graphs, and that Independent Set is W-hard in in unit-disk graphs. These results also imply that these problems have no EPTAS.
|C12||Nov. 27 & 29||[+] 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.
|C13||Dec. 4 & 6||[+] Free-For-All|
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. In addition, I'll present the 1-page slide summaries of the presentations to come in the final two class sessions.
|C14||Dec. 11 & 13||[+] Student Presentations (room TBD)|
|L22||[+] 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.
|L23||[+] 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.
|L24||[+] 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.
|Videography:||Martin Demaine||Equipment: Video shot with a Canon XA20 camera using a Sachtler Ace M Fluid Head with aluminum tripod. Lecture audio recorded using Countryman IsoMax E6 EarSet Microphone on camera using Sennheiser EW 112-p G3 wireless microphone system, and audience audio recorded using Zoom H4n. See our guide to recording video lectures.|