Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy

Abstract

Lower bounds on circuit size were previously established for functions
in Sigma^p_2, ZPP^NP, Sigma^exp_2, ZPEXP^NP and MA_exp. We investigate
the general question: Given a time bound f(n). What is the best circuit
size lower bound that can be shown for the classes MA-TIME[f],
ZP-TIME^NP[f], . . . using the techniques currently known? For the
classes MA_exp, ZPEXP^NP, and Sigma^exp_2 , the answer we get is
"half-exponential". Informally, a function f is said to be half-exponential if
f composed with itself is exponential