Die Kolmogorow-Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt somit eine beste Komprimierung der Zeichenkette an, ohne dass Information verloren geht.
Wenn die Kolmogorow-Komplexität einer Zeichenkette mindestens so groß ist wie die Zeichenkette selbst, dann bezeichnet man die Zeichenkette als unkomprimierbar, zufällig oder auch strukturlos. Je näher die Kolmogorow-Komplexität an der Länge der Zeichenkette liegt, desto 'zufälliger' ist die Zeichenkette (und desto mehr Information enthält sie).
Das Prinzip der Kolmogorow-Komplexität wurde unabhängig im Jahre 1964 von Ray Solomonoff, im Jahre 1965 von Andrei Kolmogorow und 1969 von Gregory Chaitin entwickelt, und hat Bezüge zur Shannonschen Informationstheorie.
Die Kolmogorow-Komplexität wird manchmal auch Algorithmische Komplexität oder Beschreibungskomplexität genannt, darf aber nicht mit der Zeit- oder Raumkomplexität von Algorithmen verwechselt werden. Etwas präziser ist die Bezeichnung Algorithmischer Informationsgehalt, die auch die Verbindung zu dem Begriff des Informationsgehalts nach Shannon herstellt. Ein verwandter, aber deutlich abzugrenzender Ansatz ist die Algorithmische Tiefe, die sich auf den Aufwand bezieht, der betrieben werden muss, um eine bestimmte Nachricht zu erzeugen oder zu entschlüsseln. Die Algorithmische Informationstheorie von Gregory Chaitin präzisiert den Ansatz Kolmogorows in Bezug auf das Maschinenmodell. Jorma Rissanen beschreibt mit der Minimum Description Length ein ähnliches Konzept, das aber auf Komprimierung der Daten aufbaut.