# Computing the Kolmogorov complexity of a string

What would be the implications for complexity theory if you could compute the Kolmogorov complexity of a string generated by a psuedorandom generator?

• It (potentially) depends on the running time of your algorithm. – Yuval Filmus Aug 25 '17 at 15:28
• 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? – William Hird Aug 25 '17 at 15:35
• I meant the running time of your algorithm for computing the Kolmogorov complexity. – Yuval Filmus Aug 25 '17 at 15:35
• 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? – Yuval Filmus Aug 25 '17 at 16:08
• @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... – Yuval Filmus Aug 25 '17 at 20:36

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.
• This is not possible (as the answer shows), so it's like asking what are the implications of $1=2$. – Ariel Aug 26 '17 at 6:21