Grundlagen der EITC/IS/CCTF Computational Complexity Theory

Da die zum Ausführen eines Algorithmus erforderliche Ressourcenmenge mit der Größe der Eingabe variiert, wird die Komplexität normalerweise als Funktion f(n) ausgedrückt, wobei n die Eingabegröße und f(n) entweder die Worst-Case-Komplexität ( die maximal erforderliche Ressourcenmenge über alle Inputs der Größe n) oder die durchschnittliche Fallkomplexität (der Durchschnitt der Ressourcenmenge über alle Inputs der Größe n). Die Anzahl der erforderlichen elementaren Operationen an einer Eingabe der Größe n wird allgemein als Zeitkomplexität angegeben, wobei angenommen wird, dass elementare Operationen auf einem bestimmten Computer eine konstante Zeit benötigen und sich nur um einen konstanten Faktor ändern, wenn sie auf einer anderen Maschine ausgeführt werden. Die Speicherkapazität, die ein Algorithmus für eine Eingabe der Größe n benötigt, wird als Raumkomplexität bezeichnet.

Zeit ist die am häufigsten betrachtete Ressource. Wenn der Begriff „Komplexität“ ohne Qualifier verwendet wird, bezieht er sich normalerweise auf die Komplexität der Zeit.

Die traditionellen Zeiteinheiten (Sekunden, Minuten usw.) werden in der Komplexitätstheorie nicht verwendet, da sie zu stark vom gewählten Computer und dem Fortschritt der Technologie abhängig sind. Zum Beispiel kann ein Computer heute einen Algorithmus wesentlich schneller ausführen als ein Computer aus den 1960er Jahren, jedoch liegt dies eher an technologischen Durchbrüchen in der Computerhardware als an einer inhärenten Qualität des Algorithmus. Das Ziel der Komplexitätstheorie besteht darin, den inhärenten Zeitbedarf von Algorithmen oder die grundlegenden Zeitbeschränkungen zu quantifizieren, die ein Algorithmus jedem Computer auferlegen würde. Dies wird erreicht, indem gezählt wird, wie viele Grundoperationen während der Berechnung ausgeführt werden. Diese Prozeduren werden im Allgemeinen als Schritte bezeichnet, da davon ausgegangen wird, dass sie auf einer bestimmten Maschine eine konstante Zeit benötigen (dh sie werden nicht von der Menge der Eingabe beeinflusst).

Eine weitere entscheidende Ressource ist die Menge an Computerspeicher, die für die Ausführung von Algorithmen erforderlich ist.

Eine weitere häufig verwendete Ressource ist die Anzahl der arithmetischen Operationen. In diesem Szenario wird der Begriff „arithmetische Komplexität“ verwendet. Die Zeitkomplexität ist im Allgemeinen das Produkt der arithmetischen Komplexität mit einem konstanten Faktor, wenn eine obere Beschränkung der Größe der binären Darstellung der Zahlen bekannt ist, die während einer Berechnung auftreten.

Die Größe der während einer Berechnung verwendeten ganzen Zahlen ist für viele Verfahren nicht beschränkt, und es ist unrealistisch anzunehmen, dass arithmetische Operationen eine feste Zeitdauer benötigen. Dadurch kann die Zeitkomplexität, auch Bitkomplexität genannt, deutlich höher sein als die arithmetische Komplexität. Die arithmetische Schwierigkeit der Berechnung der Determinante einer ganzzahligen nn-Matrix ist beispielsweise O(n^3) für Standardtechniken (Gaußsche Elimination). Da sich die Größe der Koeffizienten während der Berechnung exponentiell ausdehnen kann, ist die Bitkomplexität der gleichen Verfahren in n exponentiell. Wenn diese Techniken in Verbindung mit multimodularer Arithmetik verwendet werden, kann die Bitkomplexität auf O(n^4) verringert werden.

Die Bitkomplexität bezieht sich formal auf die Anzahl von Operationen an Bits, die zum Ausführen eines Algorithmus erforderlich sind. Sie entspricht der zeitlichen Komplexität bis auf einen konstanten Faktor in den meisten Berechnungsparadigmen. Die Anzahl der von Computern benötigten Operationen an Maschinenwörtern ist proportional zur Bitkomplexität. Für realistische Berechnungsmodelle sind somit die Zeitkomplexität und die Bitkomplexität identisch.

Die Ressource, die beim Sortieren und Suchen häufig berücksichtigt wird, ist die Anzahl der Vergleiche von Einträgen. Wenn die Daten gut geordnet sind, ist dies ein guter Indikator für die zeitliche Komplexität.

Bei allen möglichen Eingaben ist es unmöglich, die Anzahl der Schritte in einem Algorithmus zu zählen. Da die Komplexität einer Eingabe mit ihrer Größe ansteigt, wird sie üblicherweise als Funktion der Größe n der Eingabe (in Bits) dargestellt, und somit ist die Komplexität eine Funktion von n. Bei gleich großen Eingaben kann die Komplexität eines Algorithmus jedoch erheblich variieren. Als Ergebnis werden routinemäßig eine Vielzahl von Komplexitätsfunktionen verwendet.

Die Worst-Case-Komplexität ist die Summe aller Komplexität für alle Inputs der Größe n, während die Average-Case-Komplexität die Summe aller Komplexitäten für alle Inputs der Größe n ist (dies ist sinnvoll, da die Anzahl der möglichen Inputs einer gegebenen Größe endlich). Bei der Verwendung des Begriffs „Komplexität“ ohne weitere Definition wird die Worst-Case-Zeitkomplexität berücksichtigt.

Die Worst-Case- und Average-Case-Komplexität sind notorisch schwer richtig zu berechnen. Darüber hinaus haben diese genauen Werte wenig praktische Anwendung, da jede Änderung des Maschinen- oder Berechnungsparadigmas die Komplexität geringfügig verändern würde. Darüber hinaus ist die Ressourcennutzung für kleine Werte von n nicht entscheidend, daher ist eine einfache Implementierung für kleine n oft attraktiver als eine geringe Komplexität.

Aus diesen Gründen wird dem Verhalten der Komplexität für hohes n die meiste Aufmerksamkeit gewidmet, d. h. seinem asymptotischen Verhalten, wenn n gegen unendlich geht. Daher wird häufig die große O-Notation verwendet, um Komplexität anzuzeigen.

Computermodelle

Die Wahl eines Berechnungsmodells, das darin besteht, die wesentlichen Operationen anzugeben, die in einer Zeiteinheit durchgeführt werden, ist entscheidend für die Bestimmung der Komplexität. Dies wird manchmal als Multitape-Turing-Maschine bezeichnet, wenn das Berechnungsparadigma nicht speziell beschrieben wird.

Ein deterministisches Berechnungsmodell ist eines, bei dem die nachfolgenden Zustände der Maschine und die auszuführenden Operationen vollständig durch den vorherigen Zustand definiert werden. Rekursive Funktionen, Lambda-Kalkül und Turing-Maschinen waren die ersten deterministischen Modelle. Random-Access-Maschinen (auch als RAM-Maschinen bekannt) sind ein beliebtes Paradigma für die Simulation realer Computer.

Wenn das Berechnungsmodell nicht definiert ist, wird normalerweise von einer Multitape-Turingmaschine ausgegangen. Auf Multitape-Turing-Maschinen ist die Zeitkomplexität für die meisten Algorithmen dieselbe wie auf RAM-Maschinen, obwohl beträchtliche Aufmerksamkeit bei der Speicherung der Daten im Speicher erforderlich sein kann, um diese Äquivalenz zu erreichen.

In einigen Schritten der Berechnung können in einem nicht-deterministischen Berechnungsmodell, wie beispielsweise nicht-deterministischen Turing-Maschinen, verschiedene Entscheidungen getroffen werden. In der Komplexitätstheorie werden alle möglichen Optionen gleichzeitig berücksichtigt, und nichtdeterministische Zeitkomplexität ist die Zeit, die erforderlich ist, wenn immer die besten Entscheidungen getroffen werden. Anders ausgedrückt, die Berechnung erfolgt gleichzeitig auf so vielen (identischen) Prozessoren wie erforderlich, und die nicht-deterministische Berechnungszeit ist die Zeit, die der erste Prozessor benötigt, um die Berechnung abzuschließen. Diese Parallelität kann im Quantencomputing genutzt werden, indem überlagerte verschränkte Zustände verwendet werden, wenn spezielle Quantenalgorithmen ausgeführt werden, wie zum Beispiel die Faktorisierung winziger Ganzzahlen nach Shor.

Auch wenn ein solches Berechnungsmodell derzeit nicht praktikabel ist, hat es theoretische Bedeutung, insbesondere in Bezug auf das P = NP-Problem, das fragt, ob die unter Verwendung von „polynomialer Zeit“ und „nicht deterministischer polynomialer Zeit“ erzeugten Komplexitätsklassen als mindestens obere Grenzen sind gleich. Auf einem deterministischen Computer erfordert die Simulation eines NP-Algorithmus „exponentielle Zeit“. Wenn eine Aufgabe in polynomieller Zeit auf einem nicht-deterministischen System gelöst werden kann, gehört sie zur NP-Schwierigkeitsklasse. Wenn ein Problem in NP liegt und nicht einfacher ist als jedes andere NP-Problem, wird es als NP-vollständig bezeichnet. Das Knapsack-Problem, das Travelling-Salesman-Problem und das Boolesche Erfüllbarkeitsproblem sind alle NP-vollständige kombinatorische Probleme. Der bekannteste Algorithmus weist für all diese Probleme eine exponentielle Komplexität auf. Wenn eines dieser Probleme in polynomieller Zeit auf einer deterministischen Maschine gelöst werden könnte, dann könnten auch alle NP-Probleme in polynomieller Zeit gelöst werden, und P = NP wäre festgelegt. Ab 2017 wird allgemein angenommen, dass P NP ist, was impliziert, dass die schlimmsten Situationen von NP-Problemen grundsätzlich schwer zu lösen sind, dh bei interessanten Eingabelängen viel länger dauern als jede mögliche Zeitspanne (Dekaden).

Paralleles und verteiltes Rechnen

Paralleles und verteiltes Rechnen beinhaltet die Aufteilung der Verarbeitung auf mehrere Prozessoren, die alle gleichzeitig arbeiten. Der grundlegende Unterschied zwischen den verschiedenen Modellen besteht in der Art und Weise, wie Daten zwischen Prozessoren gesendet werden. Die Datenübertragung zwischen Prozessoren ist beim parallelen Rechnen typischerweise sehr schnell, wohingegen die Datenübertragung zwischen den Prozessoren beim verteilten Rechnen über ein Netzwerk erfolgt und somit wesentlich langsamer ist.

Eine Berechnung auf N Prozessoren benötigt mindestens den Quotienten von N der Zeit, die sie auf einem einzelnen Prozessor benötigt. Da einige Teilaufgaben nicht parallelisiert werden können und einige Prozessoren möglicherweise auf ein Ergebnis von einem anderen Prozessor warten müssen, wird diese theoretisch ideale Grenze in Wirklichkeit nie erreicht.

Das Hauptproblem der Komplexität besteht daher darin, Algorithmen zu entwickeln, damit das Produkt der Rechenzeit durch die Anzahl der Prozessoren so nah wie möglich an der Zeit ist, die erforderlich ist, um dieselbe Berechnung auf einem einzelnen Prozessor durchzuführen.

Quantenberechnung

Ein Quantencomputer ist ein Computer mit einem quantenmechanischen Rechenmodell. Für Quantencomputer gilt die Church-Turing-These, die besagt, dass jedes Problem, das ein Quantencomputer lösen kann, auch von einer Turing-Maschine gelöst werden kann. Einige Aufgaben könnten jedoch theoretisch mit einem Quantencomputer und nicht mit einem klassischen Computer mit deutlich geringerer zeitlicher Komplexität gelöst werden. Dies ist vorerst rein theoretisch, da niemand weiß, wie man einen praktischen Quantencomputer entwickelt.

Die Quantenkomplexitätstheorie wurde entwickelt, um die verschiedenen Arten von Problemen zu untersuchen, die von Quantencomputern gelöst werden können. Es wird in der Post-Quanten-Kryptografie verwendet, bei der kryptografische Protokolle erstellt werden, die gegen Angriffe auf Quantencomputer resistent sind.

Komplexität des Problems (untere Schranken)

Die Komplexität der Algorithmen, die das Problem lösen können, einschließlich unentdeckter Techniken, ist die Komplexität des Problems. Als Ergebnis ist die Komplexität eines Problems gleich der Komplexität jedes Algorithmus, der es löst.

Als Ergebnis repräsentiert jede in großer O-Notation angegebene Komplexität eine Komplexität sowohl des Algorithmus als auch des begleitenden Problems.

Andererseits ist es oft schwierig, nichttriviale untere Schranken für die Problemkomplexität zu erhalten, und dafür gibt es nur wenige Strategien.

Um die meisten Probleme zu lösen, müssen alle Eingabedaten gelesen werden, was proportional zur Größe der Daten Zeit in Anspruch nimmt. Als Ergebnis haben solche Probleme mindestens eine lineare Komplexität oder, in Big-Omega-Notation, eine Komplexität von Ω(n).

Für einige Probleme, wie die der Computeralgebra und der computeralgebraischen Geometrie, gibt es sehr umfangreiche Lösungen. Da die Ausgabe geschrieben werden muss, wird die Komplexität durch die maximale Größe der Ausgabe eingeschränkt.

Die für einen Sortieralgorithmus erforderliche Anzahl von Vergleichen hat eine nichtlineare untere Schranke von (nlogn). Als Ergebnis sind die besten Sortieralgorithmen die effizientesten, da ihre Komplexität O(nlogn) beträgt. Die Tatsache, dass es n! Möglichkeiten, n Dinge zu organisieren, führt zu dieser unteren Schranke. Da jeder Vergleich diese Sammlung von n teilt! Ordnungen in zwei Teile zerlegt, muss die Anzahl von N Vergleichen, die erforderlich ist, um alle Ordnungen zu unterscheiden, 2N > n! sein, was O(nlogn) nach der Stirling-Formel impliziert.

Das Reduzieren eines Problems auf ein anderes Problem ist eine übliche Strategie zum Erhalten von Beschränkungen der reduzierten Komplexität.

Algorithmenentwicklung

Die Bewertung der Komplexität eines Algorithmus ist ein wichtiges Element des Entwurfsprozesses, da sie nützliche Informationen über die zu erwartende Leistung liefert.

Es ist ein häufiges Missverständnis, dass aufgrund des Mooreschen Gesetzes, das das exponentielle Wachstum moderner Computerleistung vorhersagt, die Bewertung der Komplexität von Algorithmen an Bedeutung verlieren wird. Dies ist falsch, da die erhöhte Leistung die Verarbeitung riesiger Datenmengen (Big Data) ermöglicht. Zum Beispiel sollte jeder Algorithmus in weniger als einer Sekunde gut funktionieren, wenn er eine Liste mit einigen Hundert Einträgen alphabetisch sortiert, wie zum Beispiel die Bibliographie eines Buches. Andererseits müssten für eine Million Einträge (zum Beispiel die Telefonnummern einer Großstadt) die grundlegenden Algorithmen, die O(n2) Vergleiche erfordern, eine Billion Vergleiche durchführen, was drei Stunden bei einer Geschwindigkeit von 10 Millionen Vergleiche pro Sekunde. Quicksort und Mergesort hingegen erfordern nur nlogn-Vergleiche (als durchschnittliche Komplexität für erstere, als Worst-Case-Komplexität für letztere). Dies ergibt etwa 30,000,000 Vergleiche für n = 1,000,000, was bei 3 Millionen Vergleichen pro Sekunde nur 10 Sekunden dauern würde.

Als Ergebnis kann die Bewertung der Komplexität die Eliminierung vieler ineffizienter Algorithmen vor der Implementierung ermöglichen. Damit lassen sich auch komplexe Algorithmen verfeinern, ohne alle möglichen Varianten testen zu müssen. Die Untersuchung der Komplexität ermöglicht es, den Aufwand zur Steigerung der Effizienz einer Implementierung zu bündeln, indem die teuersten Schritte eines komplexen Algorithmus bestimmt werden.