1
$\begingroup$

Is the Kolmogorov complexity of any piece of information with respect to a certain predefined encoding for all pieces of information, or can the encoding vary for each piece of information?

There are different encoding mechanisms for representing data, and different ways of compressing the encoded data. If Kolmogorov complexity was encoding agnostic, then wouldn't the shortest computer program to describe each information be "0" or "1" and a call to the encoding system where each encoding system maps "0" or "1" to pieces of information of arbitrary length (the number of encoding systems would be $\frac{n}{2}$, where $n$ is the umber of pieces of information being considered). We could also increase the length of the description string, and reduce the number of encoding systems, but I think my point stands. This seems like a trivial notion of Kolmogorov complexity--is there anything I'm missing?

$\endgroup$
  • $\begingroup$ Aren't you just raising the problem an order? Your way, there's a one-to-one correspondence between strings and encoding schemes, with each encoding scheme representing the characteristic function of its associated string. So the program complexity is now just: given a string, determine which encoding scheme represents it. And as YuvalFilmus pointed out, that complexity will necessarily be the same (modulo a constant) as the string's Kolmogorov complexity (in its original, say binary or ascii, etc, encoding). $\endgroup$ – John Forkosh Jul 12 '17 at 0:33
3
$\begingroup$

The formal version of your statement is known as the invariance theorem, which states (informally) that any two definitions of Kolmogorov complexity differ by at most a constant. This issue is covered on any textbook or lecture notes on Kolmogorov complexity.

$\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.