Akademik

Komplexität,

 

Maß für den zur Ausführung eines Algorithmus bzw. zur Berechnung einer Funktion erforderlichen Rechenaufwand. Darunter wird hauptsächlich der Speicherbedarf und die Rechenzeit verstanden. Einem Problem schreibt man die Komplexität zu, die der am wenigsten rechenaufwendige Algorithmus zur Lösung des Problems aufweist. Die Komplexitätstheorie ist das Forschungsgebiet der Mathematik, in dem man sich mit dem Rechenaufwand, der Komplexität von Algorithmen beschäftigt. Hauptziel ist es, zu einem Problem den Algorithmus mit dem geringsten Aufwand zu ermitteln. Meist lassen sich Laufzeit und Speicherplatzbedarf nicht gleichzeitig minimieren; Algorithmen mit möglichst kurzer Laufzeit haben meist einen hohen Speicherbedarf und umgekehrt (engl. time-space-trade-off).

 

Man unterscheidet das Komplexitätsverhalten von Algorithmen im schlimmsten Fall (engl. worst case complexity) und im Mittel (engl. average case complexity). Die Worst-Case-Komplexität ist die maximale Laufzeit bzw. der maximale Speicherplatzbedarf, welche bei einer Eingabe auftreten können. Oft lässt sich eine Wahrscheinlichkeitsverteilung angeben, welche die Häufigkeit der verschiedenen Eingabewerte beschreibt. Die Average-Case-Komplexität ist dann das gemäß der Wahrscheinlichkeitsverteilung gewichtete Mittel der Laufzeit bzw. des Speicherplatzbedarfs für alle Eingaben.

 

Die verschiedenen Grade von Komplexität werden in Komplexitätsklassen geordnet. Die einzelnen Klassen sind ineinander geschachtelt, und zwar so, dass die Algorithmen einer untergeordneten Klasse keine höhere Komplexität aufweisen als die Algorithmen einer übergeordneten Klasse, wobei eine höhere Komplexität mit höherem Rechenaufwand verbunden ist (eine Klasse kann also Algorithmen unterschiedlicher Komplexität enthalten). Die Klasse, in welcher alle deterministischen Algorithmen Aufnahme finden, ist eingebettet in eine umfassende Klasse, die auch alle nicht deterministischen Algorithmen aufnimmt (Determinismus). Unterklassen dieser beiden übergeordneten Klassen sind die Komplexitätsklassen für die Laufzeit und für den Speicherplatz. Dabei muss man der Laufzeit eines Algorithmus häufig eine größere Komplexität zuweisen als dem Speicherplatzbedarf, da Zugriffe auf Speicherzellen stets auch Zeit benötigen. Im Folgenden wird daher vorrangig die Laufzeit von Algorithmen betrachtet.

 

Entscheidend für die Laufzeitkomplexität eines Algorithmus ist die Art und Weise, wie die Laufzeit bei Veränderung der Eingabeparameter anwächst. Als robustes Maß hat sich die Abhängigkeit der Laufzeit von der Länge der Eingabe herauskristallisiert, also der Anzahl Bits, die benötigt werden, um die Eingabe zu speichern. Günstig für praktische Berechnungen und von geringer Komplexität sind Algorithmen, deren Laufzeit höchstens linear mit wachsender Eingabelänge zunimmt. Dazu gehören z. B. Algorithmen zur Addition zweier Zahlen im Binärsystem. Alle deterministischen Algorithmen, bei denen die Anzahl der Rechenschritte wenigstens durch ein beliebiges Polynom (also eine mathematische Funktion der Variablen x der Form a + bx + cx² +..., x bezeichnet die Länge der Eingabe, a, b, c sind reelle Zahlen) beschränkt ist, fasst man in der Komplexitätsklasse P zusammen, ebenso die Probleme, die durch solche Algorithmen gelöst werden können. Darunter fällt zum Beispiel die Multiplikation zweier Zahlen im Binärsystem, bei der die Anzahl der Rechenschritte quadratisch von der Zahlenlänge abhängt (also Polynom zweiten Grades). Diese Klasse P ist besonders wichtig, weil die Algorithmen dieser Klasse in der Praxis mit vertretbarem Aufwand eingesetzt werden können. Sie wird auch als Klasse der effizient lösbaren Probleme bezeichnet. Weitaus aufwendiger sind Algorithmen mit exponentieller Laufzeit (Rechenzeit 2^cx, x bezeichnet die Länge der Eingabe, c ist eine positive reelle Zahl). Da eine um ein Bit längere Eingabe etwa eine Verdoppelung der Laufzeit nach sich zieht, sind Probleme, für die nur Exponentialzeitalgorithmen existieren, praktisch nicht lösbar. Die Komplexitätsklasse NP umfasst die Probleme, die mit nicht deterministischen Algorithmen in polynomialer Laufzeit abgearbeitet werden können. Dazu gehören alle Probleme der Klasse P, aber auch solche, zu deren Lösung keine effizienten deterministischen Algorithmen bekannt sind, z. B. das Handlungsreisendenproblem. Man begnügt sich bei Problemen der letzteren Art mit Lösungsalgorithmen, die die richtige Lösung des Problems mehr oder weniger zu erraten suchen. Eine Besonderheit der NP-Probleme besteht darin, dass einmal gefundene Lösungen sich effizient auf ihre Richtigkeit nachprüfen lassen. Bisher ist nicht bewiesen, ob zur Lösung der schwierigen NP-Probleme nicht doch Algorithmen der Komplexitätsklasse P existieren. Dieser Sachverhalt wird P=NP-Problem genannt und stellt ein herausragendes ungelöstes Problem der Informatik und Mathematik dar.