ECCC-Report TR06-080https://eccc.weizmann.ac.il/report/2006/080Comments and Revisions published for TR06-080en-usWed, 21 Jun 2006 19:52:03 +0300
Paper TR06-080
| Dimension Extractors |
David Doty
https://eccc.weizmann.ac.il/report/2006/080 A dimension extractor is an algorithm designed to increase the effective dimension -- i.e., the computational information density -- of an infinite sequence. A constructive dimension extractor is exhibited by showing that every sequence of positive constructive dimension is Turing equivalent to a sequence of constructive strong dimension arbitrarily close to 1. Similar results are shown for computable dimension and truth-table equivalence, and for p_ispace dimension and p_ispace Turing equivalence, where p_ispace represents Lutz's hierarchy of super-polynomial space bounds. Thus, with respect to constructive, computable, and p_ispace information density, any sequence in which almost every prefix has information density bounded away from zero can be used to compute a sequence in which infinitely many prefixes have information density that is nearly maximal. In the constructive dimension case, the reduction is uniform with respect to the input sequence: a single oracle Turing machine, taking as input a rational upper bound on the dimension of the input sequence, works for every input sequence of positive constructive dimension.
As an application, the resource-bounded extractors are used to characterize the computable dimension of individual sequences in terms of compression via truth-table reductions and to characterize the p_ispace dimension of individual sequences in terms of compression via p_ispace-bounded Turing reductions, in analogy to previous known results connecting effective dimensions to compression with effective reductions.
Wed, 21 Jun 2006 19:52:03 +0300https://eccc.weizmann.ac.il/report/2006/080