A better complexity of finite squences

BECHER, VERÓNICA; HEIBER, PABLO

Cape Town

Conferencia; Computability Complexity and Randomness; 2011

University of Cape Town

A better complexity of finite sequencesWe present a new complexity function defined from combinatorialproperties of strings, and we prove that not only it satisfiesfundamental properties of program-size complexity, but also itis computable in linear time and space.Our complexity function is defined by giving a scorefor each symbol in a string according to how many newsubstrings are given raised by that symbol.The accumulation of the single scores yields aglobal indicator of the repeated substrings in the given string.The most complex strings are those having the largestnumber of different substrings, the de Bruijn strings.The least complex are the runs of a single symbol.Our function is monotone in the prefix ordering of strings,and subadditive for concatenation.We prove an upper bound of the number of strings with complexityup to a given value, and we show that most strings of any given lengthhave almost maximal complexity.With these results we argue for the usefulness our complexity functionin practice, as it overcomes the drawbacks of Lempel Ziv complexity,the lack of subadditivity of approximations of Kolmogorov complexitybased on compressors,  and the absence of efficient algorithms tocompute resource-bounded versions of Kolmogorov complexity.