Complexity and Diversity
Talkat 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing · 2021-02-11..05-13
summary
Argues that modular counting for SAT resists one-shot determinant-style reductions by combining counting with linear algebra constraints: the Grassmann‑Plücker / matchgate relations force a bottleneck on how many subfunctions a local interface can present, so matchgate identities rule out broad NP‑completeness for elementary Karp reductions that compose local gadgets into a single determinant or perfect‑matching evaluation. Gives gadget constructions (match grids), uses planarity/FKT to assemble them, notes Ben Edelman’s input‑repetition trick collapses diversity and Chun‑Yi Tsai’s interpolation construction shows the Cook‑reduction case remains open.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:09Complexity and diversity
- 4:09Defining functional diversity
- 9:01Examples of functional diversity
- 13:27Representation dependency
- 17:07Linear algebra constraints
- 21:37Match gates and composition
- 27:21Lower bound argument
- 30:40Polynomial interpolation
- 33:17Boundary problems and conclusion
- 37:12Q&A session