Randomness is hard
| Author(s) : | Leen Torenvliet Harry Buhrman, |
| Publisher : | N/A |
| Publication Date : | 2000 |
| ISSN : | N/A |
| Abstract : | We study the set of incompressible strings for various resource bounded versions of Kolmogorov complexity. The resource bounded versions of Kolmogorov complexity we study are: polynomial time CD complexity dened by Sipser, the nondeterministic variant due to Buhrman and Fortnow, and the polynomial space bounded Kolmogorov complexity, CS introduced by Hartmanis. For all of these measures we dene the set of random strings R CD, |