Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-060 | 30th May 2005 00:00

Generic Density and Small Span Theorem


Authors: Philippe Moser
Publication: 4th June 2005 04:50
Downloads: 1308


We refine the genericity concept of Ambos-Spies et al, by assigning a real number in $[0,1]$ to every generic set, called its generic density.
We construct sets of generic density any E-computable real in $[0,1]$.
We also introduce strong generic density, and show that it is related to packing dimension.
We show that all four notions are different.
We show that whereas dimension notions depend on the underlying probability measure, generic density does not, which implies that every dimension result proved by generic density arguments,
simultaneously holds under any (biased coin based) probability measure.
We prove such a result: we improve the small span theorem of Juedes and Lutz to the packing dimension setting, for $k$-bounded-truth-table reductions, under any (biased coin) probability measure.

ISSN 1433-8092 | Imprint