Generalized Kolmogorov Complexity and the Structure of Feasible Computations

Abstract

In this paper we define a generalized, two-parameter, Kolmogorov complexity of finite strings which measures how much and how fast a string can be compressed and we show that this string complexity measure is an efficient tool for the study of computational complexity. The advantage of this approach is that it not only classifies strings as random or not random, but measures the amount of randomness detectable in a given time. This permits the study how computations change the amount of randomness of finite strings and thus establish a direct link between computational complexity and generalized Kolmogorov complexity of strings. This approach gives a new viewpoint for computational complexity theory, yields natural formulations of new problems and yields new results about the structure of feasible computations.