A note on dimensions of polynomial size circuits
arXiv:cs/0404044 · doi:10.1016/j.tcs.2006.02.022
Abstract
In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every , $\Ppoly$ has 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).
11 pages