Total Function Problems in the Polynomial Hierarchy
Talkat 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing · 2021-02-11..05-13
summary
Defines total search problems beyond NP, locates a new union‑bound class (PEP/APEP) and proposes the circuit‑complexity construction "complexity" as the hardest explicit task; recent work proves an epsilon‑hard problem is APEP‑complete under FP‑to‑NP reductions. Shows Nash equilibrium is PPAD‑complete and hard to approximate, places Succinct King and Sauer‑Shelah/Shor’s lemma at TFΣ3 with exact oracle types, and exhibits reductions and oracle separations used to position these problems.
AI-written summary · about