Profundidade lógica

Lógica de profundidade é uma medida de complexidade concebida por Charles H. Bennett, com base na complexidade computacional de um algoritmo que pode recriar uma determinada quantidade de informação. Ele difere do teste de Kolmogorov complexidade porque considera algoritmos com curto tempo de computação em vez de basear-se apenas em seu comprimento.

• Complexidade Efetiva
• Auto-dessimilaridade
• Previsão de complexidade
• Sofisticação (teoria da complexidade)

• 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 
• Craig, Edward (1998), «Computability and Information, Section 6: Logical depth», Routledge Encyclopedia of Philosophy, Vol. 10: Index, ISBN 9780415073103, Taylor & Francis, p. 481 
• Mitchell, Melanie (2009), «Complexity as Logical Depth», Complexity: A Guided Tour, ISBN 9780199741021, Oxford University Press, pp. 100–101