2021/06/02 by Korten, Oliver · 6 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2106.00875
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 \bfAPEPP, 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 \bfAPEPP under \bfP^\bfNP reductions. This illustrates that Shannon's classical proof of the existence of hard boolean functions is in fact a universal probabilistic existence argument: derandomizing his proof implies a generic derandomization of the probabilistic method. As a corollary, we prove that \bfEXP^\bfNP contains a language of circuit complexity 2^nΩ(1) if and only if it contains a language of circuit complexity (2n)/(2n). Finally, for several of the problems shown to lie in \bfAPEPP, we demonstrate direct polynomial time reductions to the explicit construction of hard truth tables.