Resource bounded symmetry of information revisited

详细信息	查看全文 | 推荐本文 |

• 作者：Troy Lee and Andrei Romashchenko
• 关键词：Kolmogorov complexity ; Symmetry of information ; Compression
• 刊名：Theoretical Computer Science
• 出版年：2005
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：2005
• 卷：345
• 期：2-3
• 页码：386-405
• 文件大小：195 K

摘要

The information contained in a string x about a string y is the difference between the Kolmogorov complexity of y and the conditional Kolmogorov complexity of y given x, i.e., I(x:y)=C(y)-C(y|x). The Kolmogorov–Levin Theorem says that I(x:y) is symmetric up to a small additive term. We investigate if this property also holds for several versions of polynomial time-bounded Kolmogorov complexity.

We study symmetry of information for some variants of distinguishing complexity CD where 01a22bc491" title="Click to view the MathML source">CD(x) is the length of a shortest program which accepts x and only x. We show relativized worlds where symmetry of information does not hold in a strong way for deterministic and nondeterministic polynomial time distinguishing complexities CD^poly and a50bb" title="Click to view the MathML source">CND^poly. On the other hand, for nondeterministic polynomial time distinguishing complexity with randomness, 01a2caf" title="Click to view the MathML source">CAMD^poly, we show that symmetry of information holds for most pairs of strings in any set in NP. Our techniques extend work of Buhrman et al. (Language compression and pseudorandom generators, in: Proc. 19th IEEE Conf. on Computational Complexity, IEEE, New York, 2004, pp. 15–28) on language compression by AM algorithms, and have the following application to the compression of samplable sources, introduced in Trevisan et al. (Compression of sample sources, in: Proc. 19th IEEE Conf. on Computational Complexity, IEEE, New York, 2004, pp. 1–15): any element x in the support of a polynomial time samplable source X can be given a description of size 1a561243028877911191">, from which x can be recovered by an AM algorithm.