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.
- Bennett, Charles H. (1988), "Logical Depth and Physical Complexity", in Herken, Rolf, The Universal Turing Machine: a Half-Century Survey, Oxford U. Press, pp. 227–257, CiteSeerX: 10
.1 .1 .70 .4331
- Craig, Edward (1998), "Computability and Information, Section 6: Logical depth", Routledge Encyclopedia of Philosophy, Vol. 10: Index, Taylor & Francis, p. 481, ISBN 9780415073103
- Mitchell, Melanie (2009), "Complexity as Logical Depth", Complexity: A Guided Tour, Oxford University Press, pp. 100–101, ISBN 9780199741021
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|