patternMinor
What's relation between Kolmogorov complexity and pseudorandomness?
Viewed 0 times
whatbetweenpseudorandomnessandrelationcomplexitykolmogorov
Problem
In a comment on this question, @Kaveh wondered whether the questioner really wanted to ask "is there a relation between strings with high Kolmogorov complexity and pseudorandomness?" This is not the question that was answered, in the end, but I would like to know the answer.
I understand that any pseudorandom sequence can be given a short description, by describing the program that generated it (as Travis M. points out in the question linked above). So in one sense the sequence such a sequence does not have high Kolmogorov complexity.
On the other hand, it seems as if there's some connection between pseudorandomness and Kolmogorov complexity. For if you didn't know the algorithm, then sequences generated by a good (passes lots of appropriate statistical tests, etc.) PRNG could not be described more briefly than by giving the sequence--on average, at least. Right? That's implicit in the kind of tests that good PRNGs have to pass: The tests are meant to rule out cycles and other regular patterns. (We can also require that the PRNG be cryptographically secure, if that helps.)
Happy to be told that I'm hopelessly confused. Just point me in the right direction.
I understand that any pseudorandom sequence can be given a short description, by describing the program that generated it (as Travis M. points out in the question linked above). So in one sense the sequence such a sequence does not have high Kolmogorov complexity.
On the other hand, it seems as if there's some connection between pseudorandomness and Kolmogorov complexity. For if you didn't know the algorithm, then sequences generated by a good (passes lots of appropriate statistical tests, etc.) PRNG could not be described more briefly than by giving the sequence--on average, at least. Right? That's implicit in the kind of tests that good PRNGs have to pass: The tests are meant to rule out cycles and other regular patterns. (We can also require that the PRNG be cryptographically secure, if that helps.)
Happy to be told that I'm hopelessly confused. Just point me in the right direction.
Solution
The standard notion of pseudorandomness is about a process. You can say that the process (the pseudorandom generator) is pseudorandom, or not. The notion of pseudorandomness of a single string is not defined; that's not something you can talk about.
Kolmogorov randomness is a property of a bit-string. You can say that a particular bit-string (sequence) is Kolmogorov-random, or not. Effectively, a bit-string is Kolmogorov-random if it has high Kolmogorov complexity, i.e., there's no program that outputs that string that's shorter than the string itself.
If you have a pseudorandom generator, then the strings it outputs are never Kolmogorov-random. Any output from the pseudorandom generator can always be generated by a short program (a program that hardcodes the seed to the pseudorandom generator, as well as the code of the pseudorandom generator itself), so isn't Kolmogorov-random.
That's the relationship.
Incidentally, Kolmogorov-random is not about knowledge of a program to generate the string. Knowledge is irrelevant. What matters is existence: whether or not exists a program that generates the string. If there exists a short program that generates the string, then the string is not Kolmogorov-random -- and this remains true even if you don't know the program, or even if it would be difficult to find the program.
You asked about compressibility. Let $G$ be a pseudorandom generator (in the standard cryptographic sense, i.e., computationally indistinguishable from true-random). There is a sense in which outputs of $G$ are compressible, and a sense in which they are not.
The outputs of $G$ are compressible, if you don't care how long the compression algorithm takes to run. Given $G$, we can construct a compression algorithm $C$ that compresses outputs from $G$ to something much shorter. The catch is that $C$ takes a very long time to run: it takes exponential time. In particular, $C$ works by exhaustively trying all possible seeds to see which is correct, and outputting the correct one. This isn't of much relevance in practice -- an algorithm whose running time exceeds the predicted lifetime of the solar system isn't of much engineering relevance -- but it does demonstrate that the outputs of $G$ are Kolmogorov-compressible and thus aren't Kolmogorov-random.
Outputs of $G$ are not compressible (with high probability), if you limit the compression algorithm's running time to something reasonable. For instance, suppose we limit $C$ to run in polynomial time, but allow $C$ to be otherwise unrestricted; then with high probability, running $C$ on the output of $G$ will not lead to any appreciable compression. (Why? Truly random bit-strings are, with high probability, not compressible by $C$. If pseudorandom outputs from $G$ were compressible, then you would obtain a polynomial-time algorithm for distinguishing outputs of $G$ from truly-random strings, which is exactly what the definition of pseudorandomness promises cannot happen.) So in practice, outputs of a pseudorandom generator are not compressible.
Maybe this helps enlighten the connection and contrast between standard pseudorandomness and Kolmogorov-randomness. Standard pseudorandomness is about fooling a fast distinguisher (say, one that runs in polynomial time). Kolmogorov-randomness is about fooling a short distinguisher (one whose source code is shorter than the pseudorandom string). "Fast" is largely orthogonal to "short"; you can have a short program that is very slow (e.g., exponential running time), and you can have a long program that is still fairly efficient (its source code is longer than the input string, but its running time is at most polynomial in the length of that string).
Kolmogorov randomness is a property of a bit-string. You can say that a particular bit-string (sequence) is Kolmogorov-random, or not. Effectively, a bit-string is Kolmogorov-random if it has high Kolmogorov complexity, i.e., there's no program that outputs that string that's shorter than the string itself.
If you have a pseudorandom generator, then the strings it outputs are never Kolmogorov-random. Any output from the pseudorandom generator can always be generated by a short program (a program that hardcodes the seed to the pseudorandom generator, as well as the code of the pseudorandom generator itself), so isn't Kolmogorov-random.
That's the relationship.
Incidentally, Kolmogorov-random is not about knowledge of a program to generate the string. Knowledge is irrelevant. What matters is existence: whether or not exists a program that generates the string. If there exists a short program that generates the string, then the string is not Kolmogorov-random -- and this remains true even if you don't know the program, or even if it would be difficult to find the program.
You asked about compressibility. Let $G$ be a pseudorandom generator (in the standard cryptographic sense, i.e., computationally indistinguishable from true-random). There is a sense in which outputs of $G$ are compressible, and a sense in which they are not.
The outputs of $G$ are compressible, if you don't care how long the compression algorithm takes to run. Given $G$, we can construct a compression algorithm $C$ that compresses outputs from $G$ to something much shorter. The catch is that $C$ takes a very long time to run: it takes exponential time. In particular, $C$ works by exhaustively trying all possible seeds to see which is correct, and outputting the correct one. This isn't of much relevance in practice -- an algorithm whose running time exceeds the predicted lifetime of the solar system isn't of much engineering relevance -- but it does demonstrate that the outputs of $G$ are Kolmogorov-compressible and thus aren't Kolmogorov-random.
Outputs of $G$ are not compressible (with high probability), if you limit the compression algorithm's running time to something reasonable. For instance, suppose we limit $C$ to run in polynomial time, but allow $C$ to be otherwise unrestricted; then with high probability, running $C$ on the output of $G$ will not lead to any appreciable compression. (Why? Truly random bit-strings are, with high probability, not compressible by $C$. If pseudorandom outputs from $G$ were compressible, then you would obtain a polynomial-time algorithm for distinguishing outputs of $G$ from truly-random strings, which is exactly what the definition of pseudorandomness promises cannot happen.) So in practice, outputs of a pseudorandom generator are not compressible.
Maybe this helps enlighten the connection and contrast between standard pseudorandomness and Kolmogorov-randomness. Standard pseudorandomness is about fooling a fast distinguisher (say, one that runs in polynomial time). Kolmogorov-randomness is about fooling a short distinguisher (one whose source code is shorter than the pseudorandom string). "Fast" is largely orthogonal to "short"; you can have a short program that is very slow (e.g., exponential running time), and you can have a long program that is still fairly efficient (its source code is longer than the input string, but its running time is at most polynomial in the length of that string).
Context
StackExchange Computer Science Q#69688, answer score: 6
Revisions (0)
No revisions yet.