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

Prof. Erik Demaine       TAs: Jeffrey Bosboom, Jayson Lynch


[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility]

Lecture 15 Video     [previous] [next] [completion form]

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

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.

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.

Download Video: 360p, 720p

Handwritten notes, page 1/9[previous page][next page][PDF]

Handwritten notes, page 1/9[previous page][next page][PDF]

Slides, page 1/10[previous page][next page][PDF]

Slide from Lecture 1. http://​erikdemaine.org/​papers/​GPC/​

Slides, page 1/10[previous page][next page][PDF]