[39] The complexity profile of a string x is the set of positive integer pairs Px = {(m, l) : A x, C(A) ≤ m, log |A| ≤ l}. A string x of length n and C(x) = k is -nonstochastic if for all (m, l) ∈ Px either m>k −  or m + l>n − .

(a) Show there exist nonstochastic strings for each n and k ≤ n but at most 2+O(log n) of them.

(b) Let x be an -nonstochastic string of length n and C(x) = k. If A x is a set such that d(A) ≤ 2n−k then C(x|A) ≤ 2 + O(log C(A) + log n).

Comments. Source: [A. Milovanov, Theor. Comput. Systems, 61:2(2017), 521–535]. Complexity profiles are used to formulate nonstochasticity instead of structure functions because the former are more precise. Hint for Item (a): existence follows from Exercise 5.5.10 about Theorem 5.5.2.

Let Ck be the number of strings of complexity at most k. The upper bound follows since C(x|Ck) ≤  + O(log n) for each nonstochastic string x of length n and C(x) = k. Hint for Item (b): use the notion and properties of Ck. The item states that if we delete some bits from x leaving at least k non-erased bits to obtain x then x can be reconstructed from x with logarithmic advice, that is, C(x|x
) = O(log n). In the cited source it is shown this provides good list-decoding codes with erasures.