A note on dimensions of polynomial size circuits

Details A note on dimensions of polynomial size circuits A note on dimensions of polynomial size circuits

2004-04-22

arxiv.org/abs/cs/0404044v2

Computer Science

Computational Complexity

11 pages

Scientific paper

10.1016/j.tcs.2006.02.022

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).

Affiliated with

Also associated with

No associations

Rating

A note on dimensions of polynomial size circuits does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A note on dimensions of polynomial size circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on dimensions of polynomial size circuits will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-661951