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{sub}3-strong dimension 0. We also show that P/poly{sup}(i.o.) has p{sub}3-dimension 1/2 and P{sub}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{sub}2, Theoret. Comput. Sci. 143(1) (1995) 149-158].