On joint conditional complexity (Entropy) |
| |
Authors: | Nikolay K Vereshchagin Andrej A Muchnik |
| |
Institution: | 1. Department of Mathematical Logic and Theory of Algorithms, Faculty of Mechanics and Mathematics, Moscow State University, Moscow, 119991, Russia
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|