Nonuniformly hard Boolean functions and uniform complexity classes

Valentine Kabanets


Uniform complexity classes are typically defined in terms of resource-bounded Turing machines, while nonuniform complexity classes in terms of families of Boolean circuits of bounded size. It is well known that superpolynomial circuit lower bounds for NP would imply that P≠NP. Interestingly, the same conclusion would follow from some weak circuit upper bounds for EXP. On the other hand, superpolynomial circuit lower bounds for EXP would imply that every BPP machine can be deterministically simulated in subexponential time. Thus, determining the exact relationship between uniform and nonuniform complexity classes is one of the most important tasks in theoretical computer science.

In this dissertation, we investigate several problems related to nonuniformly hard Boolean functions and uniform complexity classes. In particular, we argue that it is unlikely that there is a deterministic polynomial-time algorithm for the following minimum circuit size problem (MCSP): given the truth table of a Boolean function f:{0,1}n → {0,1} and a parameter s, decide whether f can be computed by a Boolean circuit of size at most s. We also argue that proving the NP-completeness of MCSP would prove that EXP contains a language of superpolynomial circuit complexity, which is an extremely difficult open problem. However, for a weaker nonuniform model of read-once branching programs, we show that EXP contains a language of nearly maximum nonuniform complexity.

Exploiting the relationship between nonuniformly hard Boolean functions and efficient pseudorandom generators, we obtain several results relating probabilistic and deterministic complexity classes. In particular, we prove that every probabilistic polynomial-time Turing machine with one-sided error can be simulated by a zero-error probabilistic subexponential-time Turing machine such that this simulation appears correct to all efficient adversaries. We also show that EXP=ZPP iff EE=ZPE, where EE and ZPE are the exponential analogues of the classes EXP and ZPP, respectively.

Finally, we define and study a generalization of BPP that has a natural complete problem: given a Boolean circuit, compute its acceptance probability. The new complexity class consists of all real-valued functions f:{0,1}n → [0,1] probabilistically approximable to within any ε>0 in time polynomial in n and 1/ε.