Was man über Komplexitätstheorie wissen sollte
Die Komplexitätstheorie ist ein Themenbereich der theoretischen Informatik, der den Entwurf und die Analyse von Algorithmen betrifft. Das Thema hat allerdings auch Relevanz für die Praxis. Was sollte man darüber wissen?
- Golo Roden
Die Komplexitätstheorie ist ein Themenbereich der theoretischen Informatik, der den Entwurf und die Analyse von Algorithmen betrifft. Das Thema hat allerdings auch Relevanz für die Praxis. Was sollte man darüber wissen?
Die Ausgangsbasis der Komplexitätstheorie ist die Aufgabe, zu einem Problem einen Algorithmus zu dessen Lösung zu finden beziehungsweise zu entwerfen. Ein solcher Algorithmus soll natürlich nach Möglichkeit "gut" sein, das heißt verschiedene Kriterien erfüllen. Dazu zählen Korrektheit und Verlässlichkeit, aber auch eine hohe Geschwindigkeit und wenig Speicherbedarf.
Gerade die Geschwindigkeit und der Speicherbedarf verhalten sich allerdings häufig gegensätzlich, sodass man die Wahl zwischen einem schnellen Algorithmus hat, der viel Speicher verbraucht, und einem langsamen, der sparsam mit dem Speicher umgeht. Im einfachsten Fall lässt sich ein Algorithmus durch Caching von berechneten Zwischenergebnissen beschleunigen, wodurch dann aber der Speicherbedarf steigt.
Eine wichtige Frage ist, wie man die Geschwindigkeit eines Algorithmus überhaupt angibt. Die Angabe einer absoluten Zeit ist häufig nicht sinnvoll, da sie zum einen von der tatsächlich verwendeten CPU, zum anderen aber auch von der Größe der Eingabe abhängt: Selbstverständlich dauert es länger, das Maximum aus einer Liste mit 1000 Elementen zu ermitteln als das aus einer Liste mit 100 Elementen.
Daher ist die grundlegende Idee der Komplexitätstheorie, die Laufzeit eines Algorithmus durch eine Funktion zu beschreiben, die von der Eingabegröße abhängt. Es geht dabei dann aber nicht um die konkreten, von der Funktion ermittelten Werte, sondern um deren Typ – also ob es sich um eine lineare, eine quadratische, kubische oder sonstige Funktion handelt.
Um diese Beschreibung angeben zu können, existiert die sogenannte O-Notation. Bei einem Algorithmus, der linearen Aufwand hat, spricht man daher von "O(n)", bei einem mit quadratischem Aufwand von "O(n^2)" und so weiter.
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
Polynomiale Komplexität
Der Aufwand, das Maximum einer Liste zu ermitteln, ist dabei linear: Da jedes Listenelement wenigstens einmal mit dem bisher gefundenen Maximum verglichen werden muss, steigt der Aufwand des Algorithmus linear mit der Anzahl der Elemente. Hingegen ist der Aufwand, aus einer Liste von Zahlen alle möglichen Paare zu bilden, quadratisch, da jedes Element mit jedem anderen Element kombiniert werden muss.
Eventuelle Faktoren werden dabei vernachlässigt. Es spielt also keine Rolle, ob ein Algorithmus eine Liste ein- oder zweimal durchlaufen muss, der Aufwand ist so oder so linear. Der Grund dafür ist, dass insbesondere für große Eingaben ein potenzieller Faktor keine Rolle spielt im Vergleich zu den möglichen Potenzen (langfristig steigt "x^2" aufgrund des Quadrats schneller als "2x" oder auch "10x").
Ein Sonderfall stellt "O(1)" dar, was für konstanten Aufwand steht: In diesem Fall braucht der Algorithmus unabhängig von der Größe der Eingabe stets gleich lang. Das ist beispielsweise beim Zugriff auf Elemente eines Array der Fall, da die Adresse des gewünschten Elements direkt berechnet werden kann und daher unabhängig von der Länge der Liste ist.
Alle bislang genannten Funktionen haben gemeinsam, dass sie sich durch ein Polynom beschreiben lassen. Algorithmen, deren Laufzeit polynomial beschrieben werden kann, gelten allgemein als "gut", da sie sich im Zweifelsfall durch eine schnellere CPU deutlich beschleunigen lassen, weshalb höhere Problemgrößen möglich werden.
Bei linearer Komplexität ermöglicht eine hundertmal so schnelle CPU beispielsweise auch das Lösen hundertmal so großer Probleme, bei quadratischer Komplexität immerhin noch zehnal so großer Probleme. Algorithmen, die mit polynomialer Laufzeit arbeiten, lassen sich daher durch mehr beziehungsweise bessere Hardware deutlich verbessern.
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
Nichtpolynomiale Komplexität
Das gilt allerdings nicht für jene Algorithmen, deren Laufzeit nichtpolynomial ist, sondern beispielsweise exponentiell. Ein Problem, für das bislang kein Algorithmus mit polynomialer Laufzeit gefunden wurde, ist das "Traveling Sales Person"-Problem (TSP). Dabei geht es um eine Handelsvertreterin oder einen Handelsvertreter, deren Aufgabe es ist, eine Reihe von Städten zu bereisen und dabei eine optimale, also möglichst kurze Route zu wählen.
Die naive Lösung, jede mögliche Route zu ermitteln und dann aus diesen die kürzeste auszuwählen, sprengt schnell alle Grenzen. Da es für die erste Stadt "n" Möglichkeiten gibt, für die zweite "n-1", für die dritte "n-2", und so weiter, lässt sich die Anzahl der möglichen Routen durch die Fakultätsfunktion berechnen, die extrem schnell steigt. Ein Algorithmus, der dieses Vorgehen wählt, hat daher eine Laufzeit, die durch die Fakultät beschrieben wird. Es ist unbekannt, ob es eine Lösung für TSP mit polynomialem Aufwand geben kann.
Das Problem an derartigen Algorithmen ist, dass auch durch deutlich leistungsstärkere CPUs keine nennenswerte Steigerung der Problemgröße möglich ist, da die Probleme beziehungsweise deren (bisherige) Lösungsansätze schlichtweg zu komplex sind.
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
P, NP & Co. als Komplexitätsklassen
Alle Probleme lassen sich in verschiedene Komplexitätsklassen kategorisieren. Die einfachste Klasse ist "P" und enthält all jene Probleme, für die ein Algorithmus mit polynomialer Laufzeit existiert. Die Klasse "NP" hingegen enthält anders als der Name nahelegt nicht jene Probleme, die in nichtpolynomialer Laufzeit lösbar sind, sondern jene Probleme, für die eine geratene Lösung in polynomialer Zeit überprüft werden kann. "NP" steht daher für "nichtdeterministisch polynomial".
Nicht alle Probleme in NP sind jedoch gleich schwierig. Es gibt besonders schwierige und sogar unlösbare, die zusammen wiederum die Klasse "NP-schwer" bilden. NP und NP-schwer überschneiden sich teilweise. Diese Schnittmenge wird wiederum als "NP-vollständig" bezeichnet. Das besondere an NP-vollständig ist, dass sich alle Probleme aus NP auf jedes beliebige NP-vollständige Problem mathematisch gesehen zurückführen lassen.
Das heißt, sollte es gelingen, ein einziges Problem aus NP-vollständig mit polynomialer Laufzeit zu lösen, wären automatisch alle Probleme aus NP in Polynomialzeit lösbar. Die Klassen P und NP wären in dem Fall identisch. Ob das der Fall ist oder nicht, ist aber offen.
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
Was ist NP-vollständig?
In diesem Sinne stellen die NP-vollständigen Probleme quasi den Ursprung von NP dar. Ein Beispiel für ein NP-vollständiges Problem wurde bereits genannt, nämlich TSP. Ein weiteres NP-vollständiges Problem ist das Knapsack-Problem, in dem es darum geht, eine Auswahl an Gegenständen einzupacken, die den Wert der eingepackten Gegenstände optimiert, allerdings unter Berücksichtigung der Tatsache, dass nicht beliebig viele Gegenstände eingepackt werden können.
Unter Umständen ist es ratsam, einen großen, aber wertvollen Gegenstand nicht zu wählen, da die Kombination aus zwei kleineren in der Summe wertvoller ist und weniger Platz im Rucksack einnimmt. Daran zeigt sich bereits die Verwandtschaft zu TSP: Auch hier kann es sinnvoll sein, einen sehr kurzen Abschnitt einer Route auszulassen und eine längere Strecke in Kauf zu nehmen. Das gilt nämlich dann, wenn der kurze Abschnitt zu einem unnötig langen Umweg an anderer Stelle führt.
Sollte es gelingen, eines der NP-vollständigen Probleme in Polynomialzeit zu lösen, wären P und NP gleich. Wenn P und NP jedoch nicht gleich sind, sind auch NP und NP-vollständig nicht gleich. NP enthält dann quasi alle "mittelschweren" Probleme.
Abgesehen davon, dass nicht bewiesen (oder widerlegt) ist, ob P und NP gleich sind, ist noch nicht einmal bewiesen, dass die Beziehung von P und NP überhaupt beweisbar ist. Das macht die Thematik besonders spannend und herausfordernd.
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
Fazit
Praxisrelevant ist das Thema vor allem deshalb, weil man für ein gegebenes Problem unter Umständen zeigen kann, dass es keine "gute" Lösung geben kann – dass es also sinnlos ist, weiter nach einer Lösung zu suchen, da man ohnehin nie eine finden wird. ()
