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