Kolmogorov-complexiteit

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Deze afbeelding laat een deel van de Mandelbrotverzameling fractal zien. Het afzonderlijk opslaan van alle 24-bit kleurpixels in dit plaatje zou 1,62 miljoen bits kosten. Een klein computerprogramma kan deze 1,62 miljoen bits reproduceren door gebruik te maken van de definitie van de Mandelbrotverzameling. Zo is de Kolmogorov-complexiteit van dit ruwe bestand dus veel minder dan 1,62 miljoen.

De Kolmogorov-complexiteit of algoritmische complexiteit (ook bekend als de beschrijvende complexiteit, Kolmogorov-Chaitin-complexiteit, stochastische complexiteit, algoritmische entropie of programmagrootte complexiteit) is de mate waarin een model of systeem in wiskundige of algoritmische termen beschreven kan worden. Dit is het beginsel van de minimale beschrijvingslengte (Minimum Description Length Principle, MDL-principe), de lengte van het kortste computerprogramma om een datastructuur te genereren. Dit onderdeel van de algoritmische informatietheorie (een deelgebied van de informatica), is genoemd naar Kolmogorov.

Neem bijvoorbeeld de volgende twee strings beide met lengte 64, elk bestaand uit alleen kleine letters, cijfers en spaties:

abababababababababababababababababababababababababababababababab
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf 

De eerste string laat een korte beschrijving in de Nederlandse taal toe, namelijk "ab 32 keer". Deze beschrijving bestaat uit 10 tekens. De tweede string heeft geen onmiddellijk opvallende eenvoudige beschrijving (gebruikmakend van dezelfde tekenset), anders dan de gehele string zelf, die uit 64 tekens bestaat.

Meer formeel gesproken is de complexiteit van een string de lengte van de kortste beschrijving van deze string in enige gegeven universele beschrijvingstaal. De gevoeligheid van de complexiteit ten opzichte van de keuze van de beschrijvingstaal is van belang. Aangetoond kan worden dat de Kolmogorov-complexiteit van een willekeurige string niet veel groter kan zijn dan de lengte van deze string zelf. Strings waarvan de Kolmogorov-complexiteit klein is in verhouding tot de grootte van de string worden niet als complex beschouwd. De notie van Kolmogorov-complexiteit gaat verrassend diep en kan worden gebruikt om onmogelijkheidsresultaten, die verwant zijn aan onvolledigheidsstellingen van Gödel en stopprobleem van Turing te stellen en te bewijzen.