What would be the implications for complexity theory if you could compute the Kolmogorov complexity of a string generated by a psuedorandom generator?
$\begingroup$
$\endgroup$
17
-
$\begingroup$ It (potentially) depends on the running time of your algorithm. $\endgroup$– Yuval FilmusCommented Aug 25, 2017 at 15:28
-
$\begingroup$ The generator is based on feedback shift registers with the length of each register being 63 bits, so running at 10mhz ( 10 million bits per second) the cycle time is around 5000 years before the cycle repeats, is that what you mean by run time? $\endgroup$– William HirdCommented Aug 25, 2017 at 15:35
-
$\begingroup$ I meant the running time of your algorithm for computing the Kolmogorov complexity. $\endgroup$– Yuval FilmusCommented Aug 25, 2017 at 15:35
-
1$\begingroup$ This is not what I asked. What is the running time of your algorithm for computing the Kolmogorov complexity of a string generated by a PRNG? $\endgroup$– Yuval FilmusCommented Aug 25, 2017 at 16:08
-
1$\begingroup$ @Ariel Yes, I guess you're right. I was under the impression that the diagonalizing program should also belong to the infinite computable set, but I guess I was just daydreaming... $\endgroup$– Yuval FilmusCommented Aug 25, 2017 at 20:36
|
Show 12 more comments
2 Answers
$\begingroup$
$\endgroup$
2
If we're talking about a generator who can handle any length $n$ seed (perhaps this is more cryptographic PRG oriented), and stretch it to some length $n'>n$ pseudorandom string, then the answer is no. The reason actually has nothing to do with the properties of PRGs, but simply relies on the fact that the output of the generator is computable, and that its range is infinite.
Kolmogorov's complexity isn't computable on any infinite recursively enumerable set of strings. To show this you can follow the standard proof of uncomputability of Kolmogorov's complexity. Since the set is infinite, it contains strings of arbitrarily high Kolmogorov's complexity, so you can write a program which enumerates them until it finds some string of high enough complexity, and then stop and output it. This was also answered in this math.se question.
-
$\begingroup$ Ariel, re-read my question: what are the implications? It's not a yes-no question. Thank you though for all the comments ! $\endgroup$ Commented Aug 26, 2017 at 0:28
-
$\begingroup$ This is not possible (as the answer shows), so it's like asking what are the implications of $1=2$. $\endgroup$– ArielCommented Aug 26, 2017 at 6:21
$\begingroup$
$\endgroup$
If the string you are talking is the potentially infinite sequence of 1s and 0s that are generated, the K-complexity of that string is the K-complexity of the generator plus the K-complexity of the seed. I don't know exactly what the implications of that are, because different generators of the same K-complexity do not necessarily have the same crypticity or even the same appearance of randomness. There is a generator called the Mersenne Twister where the underlying order is much more difficult to exploit than most algorithms of comparable length. Generally speaking, a small enough K-complexity of the generator could mean that there is a severe limitation on the crypticity of the sequence, but I don't believe that it's easy to characterize that relationship. In theory, I think one could make the output of a PRNG so cryptic so that one would need either a very long portion of the sequence or details of the algorithm in order to distinguish it from a typical result of a true random process.
In principle, there is no algorithm that can reliably distinguish the difference between a pseudorandom sequence and a random sequence just as there is no algorithm that can reliably estimate the K-complexity for very cryptic strings. If you tried to compress a PDF where the pages were stocked with the first billion digits of pi, the actual K-complexity would be much smaller than the size of the zip file. If this is closer to what you are asking, then perhaps you are actually asking what would happen if there were an algorithm for accurately computing K-complexity for ANY string based on some universal machine M? In that case I would expect it might force some contradictory results for computer science and make complexity theory incomprehensible. I don't see how you can necessarily categorize PRNGs as categorically different from general programs that output strings.
