Algorithmische Komplexität, die auch Kolmogorov Komplexität genannt wird, versucht den Informationsgehalt gegebener Daten zu messen. 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 die Zeichenkette z erzeugt:
- K(z) = minC(p) = z |p|
In der Praxis ist es oft nicht möglich, das kürzeste Programm anzugeben, sondern nur Abschätzungen machen.