Algorithmische Komplexität (Rechenkomplexität oder Kolmogorov-Komplexität) ist eine grundlegende Idee sowohl in der Rechenkomplexitätstheorie als auch in der algorithmischen Informationstheorie und spielt eine wichtige Rolle bei der formalen Induktion.
Die algorithmische Komplexität eines Binärstrings wird als das kürzeste und effizienteste Programm definiert, das den String erzeugen kann. Obwohl es eine unendliche Anzahl von Programmen gibt, die eine beliebige Zeichenfolge erzeugen können, ist ein Programm oder eine Gruppe von Programmen immer die kürzeste. Es gibt keinen algorithmischen Weg, den kürzesten Algorithmus zu finden, der einen gegebenen String ausgibt; Dies ist eines der ersten Ergebnisse der Computational Complexity Theory. Trotzdem können wir eine fundierte Vermutung anstellen. Dieses Ergebnis (die Rechenkomplexität eines Strings) erweist sich als sehr wichtig für Beweise im Zusammenhang mit der Berechenbarkeit.
Da im Prinzip jedes physikalische Objekt oder jede Eigenschaft durch eine Reihe von Bits bis zur Erschöpfung beschrieben werden kann, kann man auch sagen, dass Objekte und Eigenschaften eine algorithmische Komplexität aufweisen. Tatsächlich ist die Reduzierung der Komplexität von Objekten der realen Welt auf Programme, die die Objekte als Ausgabe erzeugen, eine Möglichkeit, das Unternehmen der Wissenschaft zu betrachten. Die komplexen Objekte um uns herum kommen in der Regel aus drei Haupterzeugungsprozessen; Entstehung, Evolution und Intelligenz, wobei die von jedem erzeugten Objekte zu einer höheren algorithmischen Komplexität neigen.
Rechenkomplexität ist ein Begriff, der in der theoretischen Informatik häufig verwendet wird, um die relative Schwierigkeit der Berechnung der Lösungen für breite Klassen mathematischer und logischer Probleme zu bestimmen. Es gibt mehr als 400 Komplexitätsklassen, und weitere Klassen werden ständig entdeckt. Die berühmte P = NP-Frage betrifft die Natur von zwei dieser Komplexitätsklassen. Komplexitätsklassen beinhalten Probleme, die weitaus schwieriger sind als alles, was man in der Mathematik bis hin zur Infinitesimalrechnung begegnen könnte. Es gibt viele vorstellbare Probleme in der Computational Complexity Theory, deren Lösung nahezu unendlich viel Zeit erfordern würde.
Algorithmische Komplexität und verwandte Konzepte wurden in den 1960er Jahren von Dutzenden von Forschern entwickelt. Andrey Kolmogorov, Ray Solomonoff und Gregory Chaitin leisteten Ende der 60er Jahre wichtige Beiträge zur algorithmischen Informationstheorie. Das Prinzip der minimalen Nachrichtenlänge, das eng mit der algorithmischen Komplexität verbunden ist, bildet einen Großteil der Grundlage für statistische und induktive Inferenz und maschinelles Lernen.