Kolmogoroff-Komplexität

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, ohne dass Information verlorengeht.

Wenn die Kolmogorow-Komplexität einer Zeichenkette mindestens so groß ist wie die Zeichenkette selber, 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 R. J. 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.

Beispiel

Ein Beispiel zur Erzeugung einer Folge von 1000 Nullen mag die Kompression veranschaulichen: Die Zahl 1000 lässt sich (in Binärform) durch 10 Bit darstellen. Bei einem gegebenen (konstanten) Programm zum Ausdrucken einer Nullfolge kann man die Kolmogorow-Komplexität einer Folge von n Nullen als "Konstante + log(n)" angeben:

Program Nullfolge (n)
 begin
   for i:= 1 to n         // im Beispiel n = 1000
    print "0"
 end 

Das obige Programm kann mit einer konstanten Anzahl an Bits kodiert werden, z.B. als Maschinencode oder als einfache Textdatei. Die Kodierung der Zahl n benötigt log(n) Bits. Die gesamte Kodierung benötigt also zusammengerechnet "Konstante + log(n)" Bits und damit für große n wesentlich weniger als n Bits. Daher ist die Nullfolge komprimierbar.

Die folgende Darstellung verdeutlicht die Komprimierbarkeit:

Program Nullfolge (n)00000000000000000000000000000
0begin00000000000000000000000000000000000000000000
00for i:= 1 to n0000000000000000000000000000000000
000print "0"00000000000000000000000000000000000000
0end0000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000

Das Programm, das die Folge mit 1000 Nullen erzeugt, nimmt kaum mehr als 5% der Folge selber ein.

Zufall oder Ordnung?

Es gibt allerdings (in diesem Sinne) auch nur scheinbar zufällige Zahlenfolgen. Beispielsweise gibt es ein kurzes Programm, welches die Dezimalentwicklung der Kreiszahl Pi in beliebiger Genauigkeit erzeugt. Damit ergibt sich ebenfalls eine Komplexität der Form "Konstante + log(n)", wobei n die Genauigkeit der Darstellung angibt.

Berechnung

Die Kolmogorow-Komplexität ist nicht berechenbar, sie ist allerdings von oben rekursiv aufzählbar.

Anwendungen

Heute findet die Kolmogorow-Komplexität Anwendung in der Informatik, der Biologie und anderen Wissenschaften, die Strukturen oder Informationen betrachten.

1. Datenkompression
2. Definition der Zufälligkeit in Zeichenketten

Literatur

• Ming Li and Paul Vitanyi: An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag, New York, (1993).
• Juraj Hromkovič: Theoretische Informatik, Teubner Verlag, Wiesbaden (3. Auflage 2007)

Weblinks

• Paul Vitanyis Webpräsenz zur Kolmogorow-Komplexität