2
$\begingroup$

Does the size of an algorithm restrict how many bitstrings it can compress, and how much it can compress the bitstrings?

Some definitions and an example to illustrate this is the case.

  • An elite program is the shortest program that outputs a particular bitstring.
  • Elite programs are generally incomputable (Kolmogorov complexity).
  • Due to the non-computability of elite programs, the most general compression algorithm is a lookup table, which maps bitstrings to their corresponding elite programs.
  • Compression power is the proportion of bitstrings with a specified length and Kolmogorov complexity that an algorithm can compress.

The following example illustrates how the algorithm size can impact its compression power.

  1. To compress a set of bitstrings of length 10 that have Kolmogorov complexity of 5, we need a lookup table of size $10 * 2^5$ bits. This table is signified by $T_1$.

  2. If our bitstrings are now length 20 and still have KC of 5, we need $20 * 2^5$ bits for our table $T_2$.

  3. If we have a table with the number of bits from #1, $T_1$, but need to compress the bitstrings from #2 to their KC length, we only have enough space to compress $\frac{T_1}{T_2}=\frac{10*2^5}{20*2^5}=\frac{10}{20}=\frac{1}{2}$ of the bitstrings. This is because to compress all bitstrings from #2 we need all the bits in $T_2$. However, we only have half that amount of bits we need in $T_1$.

  4. Similarly, if the KC of the bitstrings increases to 6 and length remains 10, we can only compress $\frac{10*2^5}{10*2^6}=\frac{1}{2}$ of the bitstrings.

An argument from this example suggests it is generally true an algorithm's size restricts its compression power.

A. The example shows if we are restricted to a simple lookup table algorithm, then as the bitstring length or KC increases, the number of bitstrings the algorithm can compress to KC length decreases.

B. Since elite programs are incomputable, modern compression algorithms that can compress arbitrarily large bitstrings appear to be a special case, and the lookup table is a better characterization of compression algorithms in general.

C. By A and B, it is generally the case the size of a compression algorithm in bits restricts its compression power.

$\endgroup$
  • $\begingroup$ I confess I didn't follow your point 3. Why can you only compress 1/2 of the bitstrings? Where did you draw that conclusion from? Can you edit the question to elaborate on that reasoning? Also, when you say "can compress", what exactly do you mean by that? Do you perhaps mean "compress to the minimal (Kolmogorov-complexity) program"? $\endgroup$ – D.W. Jan 16 '17 at 3:57
  • $\begingroup$ @D.W. Thanks for the comment. I have clarified point 3 as you requested, and stated compress to KC length (minimal program). $\endgroup$ – yters Jan 16 '17 at 21:13
  • 1
    $\begingroup$ This argument seems to have an unstated premise that only optimal compression matters. I think that rather than modern compression algorithms being a special case, they are a result of relaxing that requirement. Restricting input to a fixed KC rather than all bitstrings of length 10 is eliminating the generality of your "most general" compression algorithm as well. $\endgroup$ – LeBleu May 10 '17 at 17:01
  • 1
    $\begingroup$ Also, your lookup table can be calculated from a list of the $2^5$ possible 5 bit programs for a specified length. Then point 3 is no longer valid, as the size of the algorithm only increases by no more than the log of the specified length. $\endgroup$ – LeBleu May 10 '17 at 17:15
  • 1
    $\begingroup$ @LeBleu Great points. It sounds like I need a lookup table of elegant programs instead of the uncompressed bitstrings. $\endgroup$ – yters May 11 '17 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.