Affiliations: Department of Computer and Information Sciences, Towson University, Baltimore, MD, USA. [email protected]
Note: [] Address for correspondence: Department of Computer and Information Sciences, Towson University, Baltimore, MD, USA The author is supported in part by NSF grant CCF 1016158. A preliminary version of this work has been presented at MFCS 2010, Brno, Czech Republic, 23-27 August and published as [19].
Abstract: 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 α dependency with a string x if C(y) − C(y | x) ≥ α. A set of strings {x1, . . . , xt} is pairwise α-independent if for all i ≠ j, C(xi) − C(xi | xj) < α. A tuple of strings (x1, . . . , xt) is mutually α-independent if C(xπ(1) . . . xπ(t)) > C(x1)+. . .+C(xt) − α, for every permutation π of [t]. We show that: • For every n-bit string x with complexity C(x) ≥ α + 7 log n, the set of n-bit strings that have α dependency with x has size at least (1/poly(n))2n−α. In case α is computable from n and C(x) ≥ α + 12 log n, the size of the same set is at least (1/C)2n−α − poly(n)2α, for some positive constant C. • There exists a set of n-bit strings A of size poly(n)2α such that any n-bit string has α-dependency with some string in A. • If the set of n-bit strings {x1, . . . , xt} is pairwise α-independent, then t ≤ poly(n)2α. This bound is tight within a poly(n) factor, because, for every n, there exists a set of n-bit strings {x1, . . . , xt} that is pairwise α-dependent with t = (1/poly(n)) · 2α (for all α ≥ 5 log n). • If the tuple of n-bit strings (x1, . . . , xt) is mutually α-independent, then t ≤ poly(n)2α (for all α ≥ 7 log n + 6).
