On joint conditional complexity (Entropy)
Nikolay Vereshchagin, Andrej Muchnik · Proceedings of the Steklov Institute of Mathematics · 2011
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 → c )∧( b → 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.