1

Assuming we found a perfect lossless data compression algorithm, can we prove that this algorithm would only be able to compress given data to a certain size?

Tsing Shi Tao
  • 139
  • 1
  • 6
  • 1
    You might be interested in this answer I just wrote for a different question -- it's not about a proof, but it addresses some to the issues involved. – joriki Jul 13 '18 at 19:07
  • 3
    You are likely reaching toward the concept of Kolmogorov complexity: https://en.wikipedia.org/wiki/Kolmogorov_complexity – forget this Jul 13 '18 at 19:08
  • @CoryGriffith I just wanted to post this link as well :) – Peter Jul 13 '18 at 19:10
  • 1
    What do you mean by "perfect"? Gives best compression for all inputs (which is easy to show is impossible)? Gives lowest average output length for inputs of length $n$, for all $n$ (which counterintuitively is achieved by the identity function, i.e. no compression at all)? Or something else? – Daniel Schepler Jul 13 '18 at 19:10
  • @DanielSchepler By perfect, I mean an algorithm such that no greater level of data compression could be possible without the compression becoming lossy. – Tsing Shi Tao Aug 08 '18 at 10:22

0 Answers0