  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 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\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 illustrates that Shannon's classical proof of the existence of hard
boolean functions is in fact a $\textit{universal}$ probabilistic existence
argument: derandomizing his proof implies a generic derandomization of the
probabilistic method. As a corollary, we prove that $\bf{EXP}^{\bf{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 $\bf{APEPP}$, we demonstrate direct
polynomial time reductions to the explicit construction of hard truth tables.
