An Additivity Theorem for Plain Kolmogorov Complexity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Theory of Computing Systems Year : 2013

An Additivity Theorem for Plain Kolmogorov Complexity

Abstract

We prove the formula C(a, b) = K(a|C(a, b)) + C(b|a,C(a, b)) + O(1) that expresses the plain complexity of a pair in terms of prefix-free and plain conditional complexities of its components.

Dates and versions

lirmm-00785244 , version 1 (05-02-2013)

Identifiers

Cite

Bruno Bauwens, Alexander Shen. An Additivity Theorem for Plain Kolmogorov Complexity. Theory of Computing Systems, 2013, 52, pp.297-302. ⟨10.1007/s00224-012-9385-4⟩. ⟨lirmm-00785244⟩
88 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More