e is an equal number of 0 and 1 bits in the string. For odd bit sequences (n odd), the conclusions are similar with all bits identical but one (minima) or with an approximately equal number of 0 and 1 bits in the string. Second, we observe that the approximated definition (Eq. (7.21)) and the exact defini- tion (Eq. (7.22)) provide nearly similar results. It is expected that the difference rapidly vanishes for string lengths n sufficiently large. Third, we observe that the complexity is generally greater than the string length n, which appears to be in contradiction with the result obtained in Eq. (7.14), i.e., n] C. Such a contradiction is lifted if we rewrite Eq. (7.21) in the form: (7.23) 7.4 Kolmogorov complexity String X Figure 7.5 Upper bound of conditional complexity for each binary strings X of length n = 7: K(x)n), as defined by Eq. (7.22) (dark symbols) and K (x I n, k), as defined by Eq. (7.24) (open symbols) with k being the number of 1s in the string. and take the limit for large n, which gives K(x) n) nf(k/n) < n = 1(x). The upper bound n = 1(x) stems from the fact that f(u) varies from zero to unity. It is a maximum for U = k/n = 0.5, which corresponds to the case where there is an equal number of 0 or 1 bits in the string. In the case where the number of 1 bits in the string is known, we have also established from the above that n, kones) log log C*+c. (7.24) It is exactly the same result as in Eq. (7.22) with log n replaced by log k (k 1). Since k < n, the upper bound of K (x | n, kones) is, therefore, lower than that of K(x)n). The comparison between the two definitions is shown in Fig. 7.5 for n = 7. We observe from the figure that K (x n, kones) has a finer structure than K (x n) as we scan the string catalog from x = 0000000 to x = 1111111, which reflects the periodic changes in the number of 1 bits within each of the strings. Consider next the following problem: given two strings x and y, what is the size of the smallest program that can output both X and y simultaneously? A first possibilit