2

Given infinite time, we could approach a string's exact Kolmogorov complexity. If we don't have infinite time, we can still calculate an upper bound on the Kolmogorov complexity of a string:

...simply compress the string s with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the length of the resulting string...(Wikipedia)

Is there an algorithm--guaranteed to terminate within a finite amount of time--that provides a tighter upper bound on Kolmogorov complexity than len(compressed string) + len(decompressor)?

Community
  • 1
  • 1
plátano plomo
  • 1,672
  • 1
  • 18
  • 26
  • 1
    Define *compression*. It's just a non-length-preserving transformation. Of course there are other approaches/transformations and it's your call if you would call it compression. Compression algorithms are just a natural thing (everyone knows) which are widely used in practice. – sascha Sep 02 '16 at 13:43
  • For the purposes of this question, I'll go with a generic definition of compression. Let compression (`C(s) = s'`) and decompression (`D(s') = s`) be functions mapping strings to strings. So, is there a better upper bound to the Kolmogorov complexity of `s` than `s' + len(D)`? – plátano plomo Sep 02 '16 at 14:27

1 Answers1

2

Unfortunately, K(x) is not approximable. There is no upper bound. Consider compressing pi. There exists a small program that produces pi, so K(pi) is very small. But "standard" compression programs (zip, etc...) can't compress pi much. So compress(pi) is large -- arbitrarily large. Hence compress(pi) - K(pi) is unbounded.

Put another way: we don't know how small K(x) could be so we can't place an upper bound on an approximation.

Ray
  • 2,974
  • 20
  • 26