On joint conditional complexity (entropy)

Nikolay K. Vereshchagin ; Andrej A. Muchnik

Informatics and Automation, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 103-118.

Résumé

The conditional Kolmogorov complexity of a word $a$ relative to a word $b$ is the minimum length of a program that prints $a$ given $b$ as an input. We generalize this notion to quadruples of strings $a,b,c,d$: their joint conditional complexity $K((a\to c)\land(b\to d))$ is defined as the minimum length of a program that transforms $a$ into $c$ and transforms $b$ into $d$. In this paper, we prove that the joint conditional complexity cannot be expressed in terms of the usual conditional (and unconditional) Kolmogorov complexity. This result provides a negative answer to the following question asked by A. Shen on a session of the Kolmogorov seminar at Moscow State University in 1994: Is there a problem of information processing whose complexity is not expressible in terms of the conditional (and unconditional) Kolmogorov complexity? We show that a similar result holds for the classical Shannon entropy. We provide two proofs of both results, an effective one and a “quasi-effective” one. Finally, we present a quasi-effective proof of a strong version of the following statement: there are two strings whose mutual information cannot be extracted. Previously, only a noneffective proof of that statement has been known.

Bibliographie

[1] Bennett C.H., Gács P., Li M., Vitanyi P.M.B., Zurek W.H., “Information distance”, IEEE Trans. Inf. Theory, 44:4 (1998), 1407–1423 | DOI | MR | Zbl

[2] Chernoff H., “A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations”, Ann. Math. Stat., 23 (1952), 493–507 | DOI | MR | Zbl

[3] Muchnik An., Romashchenko A., Shen A., Vereshchagin N., “Upper semilattice of binary strings with the relation "$x$ is simple conditional to $y$"”, Computational complexity, Proc. 14th Annu. IEEE Conf., Atlanta, May 4–6, 1999, IEEE Comput. Soc. Press, Los Alamitos, CA, 1999, 114–122 | MR

[4] Muchnik A., Vereshchagin N., “Logical operations and Kolmogorov complexity. II”, Computational complexity, Proc. 16th Annu. IEEE Conf., Chicago, June 2001, IEEE Comput. Soc. Press, Los Alamitos, CA, 2001, 256–265

[5] Muchnik An., Vereshchagin N., “Shannon entropy vs. Kolmogorov complexity”, Computer science—theory and applications, Proc. First Intern. Symp. CSR 2006, St. Petersburg (Russia), June 8–12, 2006, Lect. Notes Comput. Sci., 3967, eds. D. Grigoriev, J. Harrison, E.A. Hirsch, Springer, Berlin, 2006, 281–291 | DOI | MR | Zbl

[6] Muchnik An.A., “Conditional complexity and codes”, Theor. Comput. Sci., 271:1–2 (2002), 97–109 | DOI | MR | Zbl

[7] Shen A., Vereshchagin N., “Logical operations and Kolmogorov complexity”, Theor. Comput. Sci., 2002:1–2, 125–129 | MR | Zbl

[8] Zvonkin A.K., Levin L.A., “Slozhnost konechnykh ob'ektov i obosnovanie ponyatii informatsii i sluchainosti s pomoschyu teorii algoritmov”, UMN, 25:6 (1970), 85–127 | MR | Zbl