## Nonuniformly hard Boolean functions and uniform complexity classes

#### Valentine Kabanets

### Abstract

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/ε.

### Versions

- PhD Thesis, University of Toronto, October 2000.