| Authors |
|
| Publication date |
2008
|
| Number of pages |
7
|
| Publisher |
Amsterdam: Institute for Logic, Language and Computation
|
| Organisations |
-
Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
|
| Abstract |
We prove that there exist finite strings with very low Kolmogorov complexity that have very high time-bounded Kolmogorov complexity. Such strings are compressible but time-bounded incompressible. For every total recursive time bound t, a constant fraction of all compressible strings is t-bounded incompressible.
|
| Document type |
Working paper
|
| Note |
Submitted to Information processing letters (Elsevier, ISSN 0020-0190)
|
| Published at |
http://arxiv.org/abs/0809.2965
|
|
Downloads
|
|
|
Permalink to this page
|
