Digital Information Retrieval
Daniel Volovici, Macarie Breazu, Daniel Ionel Morariu, Adi-Cristina Mitea · Studies in Informatics and Control · 2010
Solomonoff suggested the idea that the complexity of a string of symbols can be defined as the length of the shortest binary program that generates that string.Then, the complexity is given by the length of the minimal description.This complexity definition is universal, independent from computer, and of a fundamental importance.Kolmogorov complexity sustains the descriptive theory of complexity.Fortunately, Kolmogorov complexity approximately equals Shannon entropy H, if the sequence is chosen at random from a distribution having the entropy H.We consider Kolmogorov complexity to be more fundamental than Shannon entropy.It is the limit of data compression and leads us to a logical consistent inference procedure.A pleasant complementary relationship between algorithmic complexity and computational complexity exists here.We can see computational complexity (time complexity) and Kolmogorov complexity (the length of the program or descriptive complexity) as two axes corresponding to the running time of the program and the length of the program.Kolmogorov complexity focuses on minimizing along the second axis and computational complexity focuses on minimizing along the first axis.Few attempts have been made to minimize simultaneous along both axes.