Conditional complexity and codes
作者： Andrej A. Muchnik
DOI: 10.1016/S0304-3975(01)00033-0
关键词: Kolmogorov complexity 、 Kolmogorov entropy 、 Mathematics 、 Binary strings 、 Information theory 、 Discrete mathematics 、 Algorithmic information theory 、 Combinatorics
摘要: Let x and y be binary strings. We prove that there exists a program p of size about K(x|y) maps tox has small complexity when is known (K(p|x)0)*#8776;0). Having in mind the parallelism between Shannon information theory algorithmic theory, one can say this result parallel to Wolf-Slepian Korner-Csiszar-Marton theorems, see (I. Csiszar J. Korner, Information Coding Theorems for Discrete Memoryless Systems, Akademiai Kiado, Budapest, 1981). show also any three stringsx,y,z length at most n shortest both z (i.e., p(y)=p(z)=x) equals max(K(x|y),K(x|z)+O(logn.
acm.org
elsevier.com
sci-hub.se 参考文章(7)
Andrei A. Muchnik, Alexei L. Semenov, Multi-conditional Descriptions and Codes in Kolmogorov Complexity Electronic Colloquium on Computational Complexity. ,vol. 7, ,(2000)
Paul Vitányi, Ming Li, An Introduction to Kolmogorov Complexity and Its Applications ,(1993)
Lance Fortnow, Sophie Laplante, Nearly Optimal Language Compression Using Extractors symposium on theoretical aspects of computer science. ,vol. 1373, pp. 84- 93 ,(1998) , 10.1007/BFB0028551
Nikolai K. Vereshchagin, Michael V. Vyugin, Independent minimum length programs to translate between given strings Theoretical Computer Science. ,vol. 271, pp. 131- 143 ,(2002) , 10.1016/S0304-3975(01)00036-6
K.Yu. Gorbunov, On a complexity of the formula A∨B ⇒C Theoretical Computer Science. ,vol. 207, pp. 383- 386 ,(1998) , 10.1016/S0304-3975(98)00074-7
C.H. Bennett, P. Gacs, Ming Li, P.M.B. Vitanyi, W.H. Zurek, Information distance IEEE Transactions on Information Theory. ,vol. 44, pp. 1407- 1423 ,(1998) , 10.1109/18.681318
N.K. Vereshchagin, M.V. Vyugin, Independent minimum length programs to translate between given strings conference on computational complexity. pp. 138- 144 ,(2000) , 10.1109/CCC.2000.856744