A note on dimensions of polynomial size circuits
In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every i >= 0, P/poly has ith-order scaled p(3)-strong dimension 0. We also show that P/poly(1.0), has p(3)-dimension 1/2 and p(3)-strong dimension 1. Our results improve previous measure results of Lutz [Almost everywhere high nonuniform complexity, J. Comput. Syst. Sci. 44(2) (1992) 220-258] and dimension results of Hitchcock and Vinodchandran [Dimension, entropy rates, and compression, in: Proc. 19th IEEE Conf. Computational Complexity, 2004, pp. 174-183, J. Comput. Syst. Sci., to appear]. Additionally, we establish a Supergale Dilation Theorem, which extends the martingale dilation technique introduced implicitly by Ambos-Spies, Terwijn, and Zheng [Resource bounded randomness and weakly complete problems, Theoret. Comput. Sci. 172(1-2) (1997) 195-207] and made explicit by Juedes and Lutz [Weak completeness in E and E-2, Theoret. Comput. Sci. 143(l) (1995) 149-158]. (C) 2006 Elsevier B.V. All rights reserved.
resource-bounded dimension resource-bounded measures circuit complexity