Kolmogorov-complexiteit

De Kolmogorov-complexiteit of algoritmische complexiteit^[1] is de mate waarin een model of systeem in wiskundige of algoritmische termen beschreven kan worden. Dit is het beginsel van de minimale beschrijvingslengte, van het Engelse Minimum Description Length Principle, de lengte van het kortste computerprogramma om een datastructuur te genereren. Dit onderdeel van de algoritmische informatietheorie, een deelgebied van de informatica, is naar de Russische wiskundige Andrej Kolmogorov genoemd, een van de grondleggers van dit gebied.

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 het Nederlands toe, namelijk ab 32 keer. Deze beschrijving bestaat uit 10 tekens. De tweede string heeft geen onmiddellijk opvallende eenvoudige beschrijving, gebruikmakend van dezelfde tekencodering, anders dan de gehele string zelf, die uit 64 tekens bestaat.

De complexiteit van een string is zo gedefinieerd 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. Het is duidelijk dat de Kolmogorov-complexiteit van een willekeurige string niet veel groter hoeft te 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 diep en kan worden gebruikt om onmogelijkheidsresultaten, die verwant zijn aan de onvolledigheidsstellingen van Gödel en het stopprobleem van Turing, te stellen en te bewijzen.

1. ↑ ook bekend als de beschrijvende complexiteit, Kolmogorov-Chaitin-complexiteit, stochastische complexiteit, algoritmische entropie of programmagrootte complexiteit