2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It (potentially) depends on the running time of your algorithm. $\endgroup$ – Yuval Filmus Aug 25 '17 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 Hird Aug 25 '17 at 15:35
  • $\begingroup$ I meant the running time of your algorithm for computing the Kolmogorov complexity. $\endgroup$ – Yuval Filmus Aug 25 '17 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 Filmus Aug 25 '17 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 Filmus Aug 25 '17 at 20:36
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – William Hird Aug 26 '17 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$ – Ariel Aug 26 '17 at 6:21

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.