Geodesic
On joint conditional complexity (entropy)
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 103-118.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{TM_2011_274_a5,
     author = {Nikolay K. Vereshchagin and Andrej A. Muchnik},
     title = {On joint conditional complexity (entropy)},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {103--118},
     publisher = {mathdoc},
     volume = {274},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TM_2011_274_a5/}
}
TY  - JOUR
AU  - Nikolay K. Vereshchagin
AU  - Andrej A. Muchnik
TI  - On joint conditional complexity (entropy)
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2011
SP  - 103
EP  - 118
VL  - 274
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TM_2011_274_a5/
LA  - ru
ID  - TM_2011_274_a5
ER  - 
%0 Journal Article
%A Nikolay K. Vereshchagin
%A Andrej A. Muchnik
%T On joint conditional complexity (entropy)
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2011
%P 103-118
%V 274
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TM_2011_274_a5/
%G ru
%F TM_2011_274_a5
Nikolay K. Vereshchagin; Andrej A. Muchnik. On joint conditional complexity (entropy). Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 103-118. http://geodesic.mathdoc.fr/item/TM_2011_274_a5/

[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