|
|||||
|
|
Extracting Kolmogorov complexity with applications to dimension zero-one laws |
|
| Authors: | Lance Fortnow John M. Hitchcock A. Pavan N.V. Vinodchandran Fengming Wang |
| Affiliation: | a Department of Computer Science, University of Chicago, USA b Department of Computer Science, University of Wyoming, USA c Department of Computer Science, Iowa State University, USA d Department of Computer Science and Engineering, University of Nebraska-Lincoln, USA e Department of Computer Science, Rutgers University, USA |
| Abstract: | We apply results on extracting randomness from independent sources to “extract” Kolmogorov complexity. For any α,?>0, given a string x with K(x)>α|x|, we show how to use a constant number of advice bits to efficiently compute another string y, |y|=Ω(|x|), with K(y)>(1-?)|y|. This result holds for both unbounded and space-bounded Kolmogorov complexity.We use the extraction procedure for space-bounded complexity to establish zero-one laws for the strong dimensions of complexity classes within ESPACE. The unbounded extraction procedure yields a zero-one law for the constructive strong dimensions of Turing degrees. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |