A note on dimensions of polynomial size circuits
| dc.creator | Gu, Xiaoyang | |
| dc.date | 2004-04-22 | |
| dc.date | 2004-04-22 | |
| dc.date.accessioned | 2026-07-07T09:23:49Z | |
| dc.date.available | 2026-07-07T09:23:49Z | |
| dc.description | In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$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). | |
| dc.description | 11 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0404044 | |
| dc.identifier | http://arxiv.org/abs/cs/0404044 | |
| dc.identifier | doi:10.1016/j.tcs.2006.02.022 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/155872 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | A note on dimensions of polynomial size circuits | |
| dc.type | text |