Existentially Polytime Theorems

on YouTube ↗55m

" summary

Defines an EP theorem as “for every x there exists y” with |y| poly(|x|) and claims NP∩coNP theorems should have polytime witnesses (conjectures factoring fits here). Gives a concrete room partition pairing on a triangulated sphere and a simple constructive algorithm that doubles steps when one inserts copies, so runtimes become exponential and the problem is conjectured PPA‑complete. Presents parity results (alternating‑color paths) and a weight 1/2^k Large‑SAT criterion: if total weight <1 a recursive literal‑setting finds a satisfying assignment.

AI-written summary · about

" chapters (8)

1. 0:00Start
2. 1:19Jack Edmonds
3. 3:54Helen Hoffman
4. 15:59The Strong Perfect Graph Theorem
5. 17:31The Four Color Theorem
6. 17:54N-Dimensional Centrifugal Complex
7. 31:57The Danish Alternating Color Parity Theorem
8. 37:57Question and Discussion Session