The Hardest Explicit Construction

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 ${\bf APEPP}$, defined originally by Kleinberg et al., is the natural complexity class associated with explicit constructions for objects whose existence follows from the probabilistic method, by proving that a host of well-studied explicit construction problems lie in this class. We then observe that a result of Je\v{r}\'{a}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 ${\bf APEPP}$ under ${\bf P}^{\bf NP}$ reductions. This demonstrates that constructing a hard truth table is a universal explicit construction problem in a concrete sense. This result in fact gives a precise algorithmic characterization of proving $2^{\Omega(n)}$ circuit lower bounds for ${\bf E}^{\bf NP}$: the complete problem for ${\bf APEPP}$ has a ${\bf P}^{\bf NP}$ algorithm if and only if such a lower bound holds. Together with our proof that pseudorandom generators can be constructed in ${\bf APEPP}$, this also yields a self-contained and significantly simplified proof of the celebrated result of Impagliazzo and Wigderson that worst-case-hard truth tables can be used to derandomize algorithms (although the conclusion is weaker as our derandomization requires an ${\bf NP}$ oracle). As another corollary of this completeness result, we show that ${\bf E}^{\bf NP}$ contains a language of circuit complexity $2^{\Omega(n)}$ if and only if it contains a language of circuit complexity $\frac{2^n}{3n}$. Finally, for several of the problems shown to lie in ${\bf APEPP}$, we demonstrate direct polynomial time reductions to the explicit construction of hard truth tables.