Counting Dependent and Independent Strings

摘要

We derive quantitative results regarding sets of n-bit strings that have different dependency or independency properties. Let C(x) be the Kolmogorov complexity of the string x. A string y has a dependency with a string x if C(y) -C(y x) > a. A set of strings {xi,..., xt} is pairwise a-independent if for all i ^ j, C(xi) -C(xi Xj) < a. A tuple of strings (xi,... ,xt) is mutually a-independent if C{xn(i) .xn(t)) > C(x) + ... + C(xt) -a, for every permutation n of [i. We show that: - For every n-bit string x with complexity C(x) > a + 71ogn, the set of n-bit strings that have a dependency with x has size at least (l/poly(n))2~(n~a). In case a is computable from n and C(x) > a + 12 log n, the size of same set is at least (1/C)2"~a -poly(n)2a, for some positive constant C. - There exists a set of n-bit strings A of size poly (n) 2a such that any n-bit string has a-dependency with some string in A. - If the set of n-bit strings {x,... ,xt} is pairwise a-independent, then t < poly(n)2a. This bound is tight within a poly(n) factor, because, for every n, there exists a set of n-bit strings {xi,... ,x{ that is pairwise a-dependent with t = (l/poly(n)) ? 2a (for all a > 51ogn). - If the tuple of n-bit strings (xi,... ,xt) is mutually a-independent, then t < poly(n)2a (for all a > 71ogn + 6).