Algorithmische Komplexität, die auch Kolmogorov Komplexität genannt wird, versucht den Informationsgehalt gegebener Daten zu messen. Sogenannte 'geordnet' Daten haben dabei eine geringere Komplexität als 'zufällige'. Der hier benutzte Begriff des Zufalls unterscheidet sich jedoch von dem in der Statistik benutzten. Letztere Wissenschaft etwa bezeichnet die Dezimalentwicklung der Kreiszahl Pi als 'zufällig', wohingegen die algorithmische Komplexität von Pi sehr gering ist.
Die formalen Methoden sind im Rahmen der Informationstheorie entwickelt worden. Daher werden Daten zuerst einmal auf solche eingeschränkt, die über einen Kanal übertragen werden können, und oft betrachtet man nur digitale Signale. Eine Verallgemeinerung auf darüber hinausgehende Typen von Daten ist problematisch.
Das Maß des Informationsgehaltes ist in dieser Theorie durch den kürzesten Algorithmus, der die Daten reproduzieren kann, gegeben. Diese Formulierung ist eng verwandt mit der Problematik der Datenkompression, die Algorithmen entwickelt, gegebene Daten aus möglichst kurzen Darstellungen wiederherzustellen. Allerdings sind Kompressionsalgorithmen nicht notwendigerweise kürzeste Algorithmen.
Formal ist die algorithmische Komplexität K(z) einer Zeichenkette z durch die Länge des kürzesten Programmes p gegeben, das auf einem Computer C (oft einer Turing-Machine) die Zeichenkette z erzeugt:
K(z) = min |p|
C(p)=z
In der Praxis ist es oft nicht möglich, das kürzeste Programm anzugeben, sondern nur Abschätzungen machen.