The Hardest Explicit Construction
Oliver Korten · 2022
We investigate the complexity of explicit construction problems, where the goal is to produce a particular object possessing some pseudorandom property in time polynomial in the size of that object. We give overwhelming evidence that APEPP, defined originally by Kleinberg et al. [12], is the natural complexity class associated with explicit constructions of objects whose existence follows from the probabilistic method, by placing a variety of such construction problems in this class. We then demonstrate that a result of Jeřábek [10] on provability in Bounded Arithmetic, when reinterpreted as a reduction between search problems, shows that constructing a truth table of high circuit complexity is complete for APEPP under NP-oracle reductions. This illustrates that Shannon's classical proof of the existence of hard boolean functions is in fact a universal probabilistic existence argument: deran-domizing his proof implies a generic derandomization of the probabilistic method. As a corollary, we prove that EXPNPcontains a language of mildly-exponential circuit complexity if and only if it contains a language of nearly maximum circuit complexity. Finally, for several of the problems shown to lie in APEPP, we demonstrate direct polynomial time reductions to the explicit construction of hard truth tables.