algorithmic relative complexity算法相对复杂.pdfVIP

Entropy 2011, 13, 902-914; doi:10.3390/ OPEN ACCESS entropy ISSN 1099-4300 /journal/entropy Article Algorithmic Relative Complexity Daniele Cerra 1,* and Mihai Datcu 1,2 1 German Aerospace Centre (DLR), Münchnerstr. 20, 82234 Wessling, Germany; E-Mail: mihai.datcu@dlr.de 2 Télécom ParisTech, rue Barrault 20, Paris F-75634, France * Author to whom correspondence should be addressed; E-Mail: daniele.cerra@. Received: 3 March 2011; in revised form: 31 March 2011 / Accepted: 1 April 2011 / Published: 19 April 2011 Abstract: Information content and compression are tightly related concepts that can be addressed through both classical and algorithmic information theories, on the basis of Shannon entropy and Kolmogorov complexity, respectively. The definition of several entities in Kolmogorov’s framework relies upon ideas from classical information theory, and these two approaches share many common traits. In this work, we expand the relations between these two frameworks by introducing algorithmic cross-complexity and relative complexity, counterparts of the cross-entropy and relative entropy (or Kullback-Leibler divergence) found in Shannon’s framework. We define the cross-complexity of an object x with respect to another object y as the amount of computational resources needed to specify x in terms of y , and the complexity of x related to y a