Resource Bounded Kolmogorov Complexity, A Link Between Computational Complexity and Information Theory

The resource bounded Kolmogorov complexity classes identify finite strings (and by extension infinite strings) according to how much we can compress and then recover the strings in a space or time bounded environment. We view the resource bounded Kolmogorov complexity classes as a link between computational complexity and information theory. Firstly, we study these classes with respect to information theory (or unbounded Kolmogorov complexity classes). Most of what we know about information theory can also be shown in a space bounded environment. Whether it also stands in a time bounded environment is an interesting problem and parallels open questions about the power of nondeterminism. Then, we investigate the structure of the classes and show the analogies and differences with the structure of computational complexity classes. For example, we build hierarchies paralleling the time and space hierarchies. We show that the exponential hierarchy collapses if and only if our parallel hierarchy collapses. Lastly, we analyse the statistical properties of random strings. Martin-Lof has shown that all strings with no short description possess all the computable statistical properties of random strings. We show that this result carries over to the space bounded Kolmogorov random strings, which pass all statistical tests using less space than the space bound. Also, allowing a little more space, we can design a test to detect all those strings. These results are further applied to the theory of pseudo-random number generators. Among other consequences, it is shown that there are some properties that no space bounded random number generator can possess. The notion of statistical tests is compared to the notion of a good pseudo-random number generator, as defined by Andrew Yao