The Hardest Explicit Construction
We investigate the complexity of explicit construction problems, where the goal is to produce a particular object of size possessing some pseudorandom property in time polynomial in . We give overwhelming evidence that , 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 under reductions. This illustrates that Shannon's classical proof of the existence of hard boolean functions is in fact a probabilistic existence argument: derandomizing his proof implies a generic derandomization of the probabilistic method. As a corollary, we prove that contains a language of circuit complexity if and only if it contains a language of circuit complexity . Finally, for several of the problems shown to lie in , we demonstrate direct polynomial time reductions to the explicit construction of hard truth tables.