The Hardest Explicit Construction

Abstract

We investigate the complexity of explicit construction problems, where the goal is to produce a particular object of size $n$ possessing some pseudorandom property in time polynomial in $n$. We give overwhelming evidence that $\mathbf{APEPP}$, defined originally by Kleinberg et al., 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 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 $\mathbf{APEPP}$ under ${\mathbf{P}}^{\mathbf{NP}}$ reductions. This illustrates that Shannon's classical proof of the existence of hard boolean functions is in fact a $\text{universal}$ probabilistic existence argument: derandomizing his proof implies a generic derandomization of the probabilistic method. As a corollary, we prove that ${\mathbf{EXP}}^{\mathbf{NP}}$ contains a language of circuit complexity $2^{n^{\Omega (1)}}$ if and only if it contains a language of circuit complexity $\frac{2^n}{2n}$. Finally, for several of the problems shown to lie in $\mathbf{APEPP}$, we demonstrate direct polynomial time reductions to the explicit construction of hard truth tables.

arXiv commentImproved parameters in first rigidity reduction, simplified Lemma 3, fixed minor typos