3 ms·
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
by strictfp 15y ago
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.
- ajuc 15y agoPRNGs 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).
- strictfp 15y agoTrue. 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?
- ajuc 15y agoNo, 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.