Abstract:
Circuit size lower bounds were previously established for functions
in NP(NP), ZPP(NP), NEXP(NP), ZEXP(NP), and MAEXP.
We ask the general question: Given a
time bound t(n). What is the best circuit size lower bound
that can be currently shown for the classes MATIME[t(n)],
ZPTIME[t(n)], ... ?
For the classes MAEXP, ZEXP(NP) and NEXP(NP),
the answer turns out to be "half-exponential".
Informally, a function f is said to be half-exponential
when f(f) is exponential.
Such functions were constructed by Szekeres.