Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: string theory

Sortuj według:

Ogranicz wyniki do:

Counting Dependent and Independent Strings

Zimand M.

Fundamenta Informaticae

2014

Vol. 131, nr 3-4

485--497

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).

Druga młodość teorii polskiego matematyka

Pawluk K.

Nowa Elektrotechnika

2008

nr 7-8 (47-48)

38--39