Logical depth

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Logical depth is a measure of complexity devised by Charles H. Bennett based on the computational complexity of an algorithm that can recreate a given piece of information. It differs from Kolmogorov complexity in that it considers the computation time of the algorithm with the shortest length, rather than its length.[1][2]

See also[edit]

References[edit]

  1. ^ Bruce Edmonds "What is Complexity"
  2. ^ Charles H. Bennett "Logical Depth and Physical Complexity", in The Universal Turing Machine: a Half-Century Survey (Oxford U. Press, Rolf Herken Ed.), pp 227-257 (1988) [1]