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.

De afbeelding geeft een voorbeeld. Die laat een deel van een fractal in de Mandelbrotverzameling zien. Het afzonderlijk opslaan van alle kleurenpixels in 24-bit in de afbeelding zou 1,62 miljoen bits kosten. Een relatief kort 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.