Kolmogorov-complexiteit

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 de Russische wiskundige Andrej 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.