# Finding Most Compressible Vector Within Bounds?

Given large positive integers $m$ and $n$:

Let $S$ be the set of integers $\{1,2,\dots,m\}$

We are given as input two vectors $L$ and $U$ both over $S^n$ such that:

$$\bigwedge_{i=1}^{n}{L_i \le U_i}$$

We are interested in the set of vectors $X$ over $S^n$ such that:

$$\bigwedge_{i=1}^{n}{L_i \le X_i \le U_i}$$

Notice that if we define $D = U - L$ than there are:

$$\prod_{i=1}^{n}(D_i+1)$$

valid $X$ vectors.

We want an algorithm that takes $L$ and $U$ and generates a self-contained program as output. That program when executed may output any one valid $X$, and be as small as possible (in terms of total code and data).

Therefore we would like to know which valid $X$ vector is the one that is the "most compressible". We can then generate a program that contains that vector compressed in its data section, and the program will simply decompress it and output it.

How can we determine which $X$ is most compressible as a function of $L$ and $U$?

-
Since the Kolmogorov complexity of a function is uncomputable, finding the "most compressible" vector is impossible. However, it's quite possible that you can find an algorithm that works reasonable well for this. – Peter Shor Nov 30 '12 at 13:34