Complexitat de Kolmogórov

Archiu:Mandelpart2 red.png

Detalle d'una part del conjunt de Mandelbrot. Almagasenar esta image en el format PNG en color de calitat 24-bit requeriria 1,69 millons de bytes; no obstant, un chicotet programa informàtic pot reproduir estos 1,69 millons de bytes usant la definició del conjunt de Mandelbrot. Per eixa raó, la complexitat de Kolmogórov és de fet molt menor que 1,69 millons de bytes.

En la teoria de la computació, la complexitat de Kolmogórov és el tamany o cantitat d'informació del programa de computadora més curt que produïx cert resultat. Deu el seu nom a Andréi Kolmogórov. La complexitat de Kolmogórov també es denomina complexitat descriptiva o complexitat de Kolmogoróv-Chaitin, complexitat estocàstica, o entropía algorítmica.

Per a definir la complexitat de Kolmogórov, primer deu especificar-se un llenguage descriptivo per a les seqüències o cadenes. Tal llenguage pot basar-se en qualsevol llenguage de programació com Lisp o Pascal. Si P és un programa que genera com eixides seqüències de tipo x, llavors P és una descripció del conjunt de x. La llongitut de la descripció és la llongitut de P com a seqüència de caràcters. Per a determinar la llongitut de P, deu donar-se conte de les llongituts de totes les subrutina amprades en P. La llongitut de qualsevol número entero n que aparega en el programa P és la cantitat de bits requerits per a representar n, açò és, log₂n.

Vore també

• Teoria algorítmica de l'informació
• Teoria de la complexitat computacional