Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential
Hierarchy
Peter Bro Miltersen
December 1999 |

## Abstract:
Lower bounds on circuit size were previously established for
functions in ,
,
,
and
. We investigate the general question: Given a time bound . What
is the best circuit size lower bound that can be shown for the classes
,
using the techniques currently known? For the classes
,
and
, the answer we get is ``half-exponential''. Informally, a function
is said to be half-exponential if composed with itself is
exponential
Available as |

Last modified: 2003-06-08 by webmaster.