Kolmogorov complexityReportar como inadecuado

Kolmogorov complexity - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LIF - Laboratoire d-informatique Fondamentale de Marseille - UMR 6166 2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : The term -complexity- has different meanings in different contexts. Computational complexity measures how much time or space is needed to perform some computational task. On the other hand, the complexity of description called also Kolmogorov complexity is the minimal number of information bits needed to define describe a given object. It may well happen that a short description requires a lot of time and space to follow it and actually construct the described object. However, when speaking about Kolmogorov complexity, we usually ignore this problem and count only the description bits. As it was common to him, Kolmogorov published, in 1965, a short note that started a new line of research. Aside from the formal definition of complexity, he has also suggested to use this notion in the foundations of probability theory.

Autor: - Alexandre Zvonkine -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados