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.
Q2623243
model
Concept
Q58778
systeem
Concept
Q8366
algoritmische
Concept
Q40056
computerprogramma
Concept
None
algoritmische informatietheorie
UNK
Q21198
informatica
Concept
Q153224
Andrej Kolmogorov
PER
Q184754
strings
Concept
Q7411
Nederlandse taal
Concept
Q3241972
tekens
Concept
Q184759
tekenset
Concept
Q723897
complexiteit
Concept
None
universele
UNK
None
beschrijvingstaal
UNK
Q200787
onvolledigheidsstellingen van Gödel
EVE
Q622849
stopprobleem
Concept
Q7251
Turing
PER
Q11538
bewijzen
Concept
Q1456811
Kolmogorov-complexiteit
Concept
Q1456811
Kolmogorov-complexiteit
Concept
Q1456811
Kolmogorov-complexiteit
Concept
Q1456811
Kolmogorov-complexiteit
Concept
+64^^http://www.w3.org/2001/XMLSchema#decimal
64
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+5^^http://www.w3.org/2001/XMLSchema#decimal
5
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
0^^http://www.w3.org/2001/XMLSchema#decimal
0
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+8^^http://www.w3.org/2001/XMLSchema#decimal
8
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+39^^http://www.w3.org/2001/XMLSchema#decimal
39
NUMBER
+5^^http://www.w3.org/2001/XMLSchema#decimal
5
NUMBER
+85^^http://www.w3.org/2001/XMLSchema#decimal
85
NUMBER
+7^^http://www.w3.org/2001/XMLSchema#decimal
7
NUMBER
0^^http://www.w3.org/2001/XMLSchema#decimal
0
NUMBER
+7^^http://www.w3.org/2001/XMLSchema#decimal
7
NUMBER
+9^^http://www.w3.org/2001/XMLSchema#decimal
9
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+32^^http://www.w3.org/2001/XMLSchema#decimal
32
NUMBER
+10^^http://www.w3.org/2001/XMLSchema#decimal
10
NUMBER
+64^^http://www.w3.org/2001/XMLSchema#decimal
64
NUMBER
named after
subclass of
notable work