Total Functions in the Polynomial Hierarchy

on YouTube ↗35m

" summary

Defines a hierarchy TFΣi of total search classes and proves specific natural problems sit at low levels: the empty problem is in TFΣ2 via a union‑bound / pigeonhole argument; introduces Alpha‑PPP (output space ≥2× input space) and shows Remote Point, Delta‑rigid matrix completion and a Shannon‑style circuit complexity search lie in Alpha‑PPP (hence in PPP variants); places shattering in PPP with a Σ2 oracle and Kings in a polynomial‑poset maximization class with an NP oracle. Main open: completeness under NP reductions.

AI-written summary · about

" chapters (17)

1. 0:00Introduction
2. 0:26Overview
3. 2:01Definition
4. 2:55TFNP
5. 5:43Empty Pigeonhole
6. 7:00T of sigma 2
7. 11:10Remote point
8. 12:48Delta rigid
9. 15:23Boolean search
10. 18:13Apppp
11. 21:11Optimization
12. 22:02Natural Problems
13. 22:42Shattering
14. 27:41Tournaments
15. 28:33Search Problem Kings
16. 31:15Conclusion
17. 32:25Questions