An Additivity Theorem for Plain Kolmogorov Complexity

作者：Bauwens Bruno^*; Shen Alexander

来源：Theory of Computing Systems, 2013, 52(2): 297-302.

DOI：10.1007/s00224-012-9385-4

• Kolmogorov complexity
• Symmetry of information
• Additivity of Kolmogorov complexity
• Plain complexity

We prove the formula C(a, b) = K(a vertical bar C(a, b)) + C(b vertical bar 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.

• 出版日期2013-2