miniatura|Detall d'una part del conjunt de Mandelbrot. Emmagatzemar aquesta imatge sense més en color de qualitat 24-bit requeriria 1,62 milions de bits; no obstant això, un petit programa informàtic pot reproduir aquests 1,62 milions de bits usant la definició del conjunt de Mandelbrot. Per aquesta raó, la complexitat de Kolmogórov és de fet molt menor que 1,62 milions de bits.
En la teoria de la computació, la complexitat de Kolmogórov és una mesura de la quantitat de recursos computacionals necessaris per a poder descriure una certa quantitat d'informació. El nom es deu a Andrei Kolgomórov. La complexitat de Kolmogórov també es denomina complexitat descriptiva o complexitat de Kolmogórov-Chaitin, complexitat estocàstica, o entropia algorítmica.
Per poder definir la complexitat de Kolmogórov, primer s'ha d'especificar un llenguatge descriptiu per a les seqüències o cadenes. Aquest llenguatge pot basar-se en qualsevol llenguatge de programació com ara Lisp o Pascal. Si P és un programa que genera com sortides seqüències de tipus x, llavors P és una descripció del conjunt de x. La longitud de la descripció és la longitud de P com a seqüència de caràcters. Per determinar la longitud de P, ha d'adonar-se de les longituds de totes les subrutines emprades en P. La longitud de qualsevol nombre enter n que aparegui en el programa P és la quantitat de bits requerits per representar n, això és, log₂n.
Definició Podem intentar comprendre la complexitat de Kolmogórov amb aquest exemple. Considerem dues cadenes de caràcters de 32 lletres minúscules i dígits:
abababababababababababababababab
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7
La primera cadena la podem definir fàcilment com a “Escriure ab 16 cops”, una “ordre” que consta de 19 caràcters en català. Per l'altra banda, la segona cadena no té una forma clara de ser definida exceptuant “Escriu 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7”, que té una longitud de 39 caràcters en català. Llavors, en aquest exemple concret, podem determinar que l'operació d'especificar la primera ordre té menys complexitat que la segona.
Més formalment, la complexitat d'una cadena de caràcters és la longitud de la descripció més curta d'aquesta en un llenguatge de descripció fix (La sensibilitat de l'elecció d'un llenguatge respecte de la complexitat es discuteix més avall). Es pot demostrar que la Complexitat de Kolmogórov d'una cadena de caràcters no pot ser major a uns bytes més que la longitud de la cadena mateixa. Una cadena com la primera de l'exemple anterior, que té una complexitat petita amb comparació a la cadena original no es considera complexa.
La complexitat de Kolmogórov pot ser definida per qualsevol objecte matemàtic, però per simplicitat només utilitzarem cadenes de caràcters. Primer hem d'especificar un llenguatge per a la descripció de les cadenes de caràcters, el llenguatge pot ser basat en qualsevol llenguatge de programació, com Lisp, Pascal o Java. Si P és un programa que produeix una cadena x, llavors P és una descripció de x. La llargada de la descripció només és la llargària de P multiplicat pel nombre de bits que ocupa cada caràcter de P.
Tota cadena de caràcters té com a mínim una manera de descriure-la. Per la segona cadena del nostre exemple tenim el programa:
funció GenerarCadena2() retornar “4c1j5b2p0cv4w1x8rx2y39umgw5q85s7”
Mentre que per la primera cadena ho podem escriure amb pseudocodi com a:
funció GenerarCadena1() retornar “ab” × 16
Si la descripció d(s) d'una cadena s és la més curta possible, s'anomena la descripció mínima ds, i la longitud de d(s) és la seva complexitat de Kolmogórov, que s'escriu com K(s). Simbòlicament, això s'expressaria com:
Encara que la longitud de la descripció més curta es pugui veure afectada per l'elecció de llenguatge de descripció, aquest efecte està fitat (com a resultat del teorema de la invariància).
Teorema de la Invariància Tractament Informal Hi ha alguns llenguatges de descripció òptims en el sentit que donada qualsevol descripció d'un objecte en un llenguatge de descripció qualsevol, aquesta descripció es pot fer servir a un llenguatge òptim amb una sobrecàrrega constant. La constant només depèn dels llenguatges involucrats, i no de l'objecte en si o la seva descripció.
Posem un exemple d'un llenguatge de descripció òptim:
La primera part defineix un altre llenguatge de descripció.
La segona part és la descripció de l'objecte en aquest llenguatge.
En termes més tècnics, la primera part és una descripció d'un programa, i la segona part és l'entrada per al programa per produir l'objecte com a sortida.
Llavors, el teorema de la invariància diu: Donat qualsevol llenguatge de descripció L, el llenguatge de descripció òptim és com a mínim igual d'eficient que L, amb una sobrecàrrega constant.
Demostració: Qualsevol descripció D en L es pot convertir en una descripció en el llenguatge òptim per, primer descriure L com un programa P (primera part), i després utilitzar la descripció D com a entrada del programa P (segona part). La longitud total d'aquesta nova descripció D' és aproximadament:
On la longitud de P és constant i, per tant, no depèn de D. Llavors, com a màxim hi ha un increment constant sense importar l'objecte que s'està descrivint. En conseqüència, el llenguatge òptim és universal fins a aquesta constant.
Tractament Formal Teorema: Si i són funcions de complexitat relatives a llenguatges de descripció Turing complets i , llavors hi ha una constant c, que depèn només dels llenguatges i agafats, tal que:
.
Demostració: Per simetria, és suficient provar que hi ha una constant c que per a totes les cadenes s.
Ara, suposem que hi ha un programa en el llenguatge que actua com un intèrpret de :
funció InterpretarLlenguatge(cadena p)
on p és un programa a . L'intèrpret es caracteritza per la següent propietat:
Córrer InterpretarLlenguatge en l'entrada p retorna el resultat d'executar p.
Per tant, si P és un programa a que és descripció mínima de s, llavors InterpretarLlenguatge(P) retorna s. La longitud d'aquesta descripció és la suma de
La longitud del programa InterpretarLlenguatge, que podem considerar la constant c. La longitud de P que, per definició, és .
Això demostra la fita superior que buscàvem.
Història i context La teoria algorísmica de la informació és l'àrea de la ciència de la computació que estudia la complexitat de Kolmogórov i altres mètriques de complexitat en strings (entre altres estructures de dades).
El concepte i la teoria darrera de la complexitat de Kolmogórov es basa en un teorema enunciat pel Ray Solomonoff, publicat l'any 1960, en l'article "A Preliminary Report on a General Theory of Inductive Inference" com a part de la seva invenció de la probabilitat algorítmica. Va acabar de donar-ne una descripció més completa en articles posteriors, amb "A Formal Theory of Inductive Inference", parts 1 i 2, dins la revista Information and Control, edicions de març i juny de 1964 respectivament.
Posteriorment, Andrei Kolgomórov va publicar independentment el mateix teorema a "Problems Inform. Transmission", l'any 1964. Gregory Chaitin presenta el teorema a "J.ACM" a un article entregat a octubre de 1966 i revisat a desembre de 1968, citant a Kolmogórov i Solomonoff.
El teorema diu que, entre els algoritmes que descodifiquen cadenes de les seves descripcions (codis), n'hi ha un d'òptim. Aquest algoritme, per a totes les cadenes, admet codis tan curts com els permet qualsevol altre algorisme fins a una constant que depèn dels algorismes, però no de les cadenes en si. Solomonoff va utilitzar aquest algorisme i les longituds de codi que permeten definir una "probabilitat universal" d'una cadena en què es pot basar la inferència inductiva dels dígits subsegüents de la cadena. Kolmogorov va usar aquest teorema per a definir diverses funcions de les cadenes, incloses la complexitat, l'aleatorietat i la informació.
Quan Kolmogórov es va adonar del treball de Solomonoff, va reconèixer la prioritat de Solomonoff. Durant diversos anys, l'obra de Solomonoff va ser més coneguda a la Unió Soviètica que al món occidental. El consens general de la comunitat científica, tanmateix, va ser associar aquest tipus de complexitat amb Kolmogórov, que es preocupava per l'aleatorietat d'una seqüència, mentre que la probabilitat algorítmica es va associar amb Solomonoff, que es va centrar en la predicció fent servir la seva invenció de la distribució de probabilitat prèvia universal. L'àrea més àmplia que inclou la complexitat descriptiva i la probabilitat s'anomena sovint complexitat de Kolmogórov. La informàtica Ming Li considera que això és un exemple de l'efecte Mateu: "... a qui més tingui, més se'n donarà..."
Hi ha diverses altres variants de la complexitat de Kolmogórov o la informació algorítmica. El més emprat es basa en programes autodelimitats, i es deu principalment a Leonid Levin (1974).
Un enfocament axiomàtic de la complexitat de Kolmogórov basat en els axiomes de Blum (Blum 1967) va ser introduït per Mark Burgin en el document presentat per a la seva publicació per Andrei Kolgomórov.
Resultats bàsics A partir d'ara utilitzarem K(s) per denotar la complexitat de la cadena s.
No resulta massa difícil veure que la descripció mínima d'una cadena no pot ser més molt més llarga que aquesta. Com s'ha pogut veure abans el programa GenerarCadena2 és només una quantitat fixa més gran que la cadena que retorna. De la mateixa manera, canviant la cadena que retorna aquest programa és fàcil de veure que aquest increment és constant.
Teorema: Hi ha una constant c tal que:
.
Incomputabilitat de la complexitat de Kolmogórov Un intent naïf d'un programa per calcular K A primera vista pot semblar trivial escriure un programa que computi K(s) per a qualsevol s, com per exemple:
funció ComplexitatDeKolmogorov (cadena s) per i = 2 fins infinit: per cada cadena p de longitud exactament i: si ésUnProgramaValid(p) i evaluar(p) == s retorna i
Aquest programa itera per tots els programes possibles començant amb els més curts i continuant amb programes cada vegada més grans. Després (si és un programa vàlid, és a dir, que el programa corre) l'executa i comptarà la seva sortida a la cadena de la qual volem calcular la seva complexitat. En cas que trobi un programa que funcioni retorna la longitud d'aquest programa.
Tot i això, aquest programa no funcionarà, ja que alguns dels programes p que provarà no pararan, per exemple si contenen bucles infinits. No hi ha cap manera d'evitar aquests programes que no sigui executar-los i esperar que finalitzin a causa de la incomputabilitat del problema de la parada.
Encara més, no hi ha cap programa que calculi K(s), sense importar que tan sofisticat sigui. Això es pot demostrar de la manera següent.
Prova formal de la incomputabilitat de K Teorema: existeixen cadenes de caràcters d'una complexitat de Kolmogórov arbitràriament gran. Formalment per cada existeix una cadena s amb K(s) ≥ n.
Prova: Si això no es complís, llavors les infinites cadenes de longitud finita podrien ser generades pels finits programes de longitud menor a n.
Teorema: K no és una funció computable, és a dir, no hi ha cap programa que donada una cadena s, doni com a resultat K(s).
En la següent prova de contradicció s'utilitza un llenguatge de pseudocodi que per simplificar se suposarà que té un intèrpret de 1000000 bits. Assumeix que existeix un programa
funció ComplexitatDeKolmogorov(cadena s)
que donada una cadena s retorna K(s). Com el programa és finit, per simplificar se suposarà que és de longitud 9000000000 bits ( bits). Ara considera el següent programa d'una longitud de no més de 64000 bits.
funció GenerarCadenaComplexa() per i = 1 fins infinit: per cada cadena s de longitud exactament i: si ComplexitatDeKolmogorov(s) > 10000000000 retorna s