Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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$?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.