Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-047 | 22nd April 2004 00:00

A note on dimensions of polynomial size circuits

RSS-Feed

Abstract:

In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$th order scaled $\pthree$-strong dimension $0$. We also show that $\Ppoly^\io$ has $\pthree$-dimension $1/2$, $\pthree$-strong dimension $1$. Our results improve previous measure results of Lutz (1992) and dimension results of Hitchcock and Vinodchandran (2004).



ISSN 1433-8092 | Imprint