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

  • Peter Bro Miltersen
  • Vinodchandran N. Variyam
  • Osamu Watanabe

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
Published
1999-12-16
How to Cite
Miltersen, P., Variyam, V., & Watanabe, O. (1999). Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy. BRICS Report Series, 6(46). https://doi.org/10.7146/brics.v6i46.20116