Re:Kolmogorov Complexity - A Primer
by strictfp on Monday April 23, 2012 @03:21AM
(#3877704)
With the given definition I assume that it would be impossible to have a Kolmogorov complexity higher than the size of the smallest PRNG program (+seed)? If so it might be of limited usefulness for larger strings.
[ Parent
| on HN ]
PRNGs are not interchangeable, they produce different subsets of all possible strings (let's define result of PRNG+seed as all the bits of generated numbers concatenated, until PRNG starts to repeat).
And any program returning something can be seen as a PRNG (at worst it won't accept seed, so it will only produce one string).
True. What you say must imply that no PRNG-generated sequence has a particularly high K complexity (> len(PRNG)). What still interests me in this scenario is that a true random source can still generate the same sequence as a PRNG. In that case the complexity of the string becomes small. So for a given true random source you can still get strings with low K complexity. Does this affect cryptography in any way?
No, because cryptography just wants to ensure that given all past bits of generator output you can't predict future bit with probability different than 0.5.
And besides, overwhelming majority of strings are random, once you got to strings long enough. Probabilty that random generator will make not Kolmogorov random string is 0.