A note on dimensions of polynomial size circuits

Abstract: In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every , has ith-order scaled -strong dimension 0. We also show that has -dimension and -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 , Theoret. Comput. Sci. 143(1) (1995) 149–158]. [Copyright &y& Elsevier]