1
$\begingroup$

Let Program P be :"Generate, in lexicographic order, all sequences with k ones and n bit length; Of these sequences, print the ith sequence."

Apparently the length of this program is $\log(n) + \log(\binom{n}{k}) + c$ where $c$ is a constant. Where $i$ can be represented in $\log(n)$ bits and k in $\log(\binom{n}{k})$ bits. Why does the length of the program not take into account that we will be generating all of these sequences in lexicographic order, does the length of the sequences and the number of sequences not depend on $n$. Don't you have to hold those in an array? Does that not take space?

Thank you.

$\endgroup$
  • $\begingroup$ You seem to have mixed $i$ and $k$ in your length estimates. Also, you're missing $n$. $\endgroup$ – Yuval Filmus Apr 22 '18 at 4:21
  • $\begingroup$ Note that we don't measure the space consumption of the program; rather, we measure its length. The program need not include a list of all possible vectors, since it can generate them on its own given the parameters $n,k$. $\endgroup$ – Yuval Filmus Apr 22 '18 at 4:22
  • $\begingroup$ @YuvalFilmus, I see. Thank you for clearing that up. $\endgroup$ – C..O..S Apr 22 '18 at 4:29
1
$\begingroup$

In Kolmogorov complexity, our measure of complexity is program length. We don't care about the resource consumption of the program (unless we're interested in resource-bounded Kolmogorov complexity). Given $n$ and $k$, a program can generate all $n$-bit strings of weight $k$, so there is no need to store the list itself as part of the program.

The formula you quote and the explanation you give seem mistaken. In order to use the program you mention to generate a specific vector, we need to give it as input $n,k,i$. It takes $K(n) \le \log n + O(\log\log n)$ bits to encode $n$ itself. Given $n$, we can encode $k$ in $\lceil \log n \rceil$ bits, and $i$ in $\lceil \log \binom{n}{k} \rceil$ bits. Overall, we obtain that the Kolmogorov complexity is at most $$ 2\log n + \log \binom{n}{k} + O(\log\log n). $$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.