A note on dimensions of polynomial size circuits
Xiaoyang Gu
Abstract
In this paper, we use resource-bounded dimension theory
to investigate polynomial size circuits.
We show that for every i ≥0,
P/poly has i th-order scaled p3-strong dimension 0.
We also show that P/polyio
has p3-dimension 1/2 and p3-strong
dimension 1. Our results improve
previous measure results of Lutz (1992) and
dimension results of Hitchcock and Vinodchandran (2004).
Additionally, we establish a Supergale Dilation Theorem,
which extends the martingale dilation technique
introduced implicitly by Ambos-Spies, Terwijn,
and Zheng (1997) and made explicit by
Juedes and Lutz (1995).
Journal Version:
-
Theoretical Computer Science, 359(1-3):176-187, 2006.
[ PS | PDF |
DOI
| BibTex
]
Last modified on August 2nd, 2006.