Was ist für einen Computer einfach und was ist fast unmöglich? Diese Fragen stehen im Mittelpunkt des Problems der Rechenkomplexität. Wir präsentieren Ihnen eine Karte dieser Landschaft.
Verschiedene Komplexitätsklassen sortieren Aufgaben in einer hierarchischen Form. Eine Klasse kann alle Aufgaben einer anderen sowie Aufgaben enthalten, für die zusätzliche Rechenressourcen erforderlich sind.Was ist die grundlegende Schwierigkeit der Aufgabe? Dies ist die Formulierung der Grundaufgabe von Informatikern, die versuchen, die Aufgaben nach den sogenannten zu sortieren.
Schwierigkeitsgrade . Hierbei handelt es sich um Gruppen, die alle Rechenaufgaben enthalten, für die nicht mehr als eine feste Menge an Rechenressourcen erforderlich ist, z. B. Zeit oder Speicher. Nehmen wir ein einfaches Beispiel mit einer großen Zahl wie 123 456 789 001. Man kann fragen: Ist es eine Primzahl - eine, die nur durch 1 und sich selbst teilt? Informatiker können dies mit schnellen Algorithmen beantworten - so dass sie bei beliebig großen Zahlen nicht langsamer werden. In unserem Fall stellt sich heraus, dass diese Zahl keine Primzahl ist. Dann können wir die Frage stellen: Was sind ihre Hauptfaktoren? Es gibt jedoch keinen schnellen Algorithmus, um dies zu beantworten - nur wenn Sie einen Quantencomputer verwenden. Informatiker glauben daher, dass diese beiden Aufgaben zu unterschiedlichen Komplexitätsklassen gehören.
Es gibt viele verschiedene Schwierigkeitsgrade, obwohl die Forscher in den meisten Fällen nicht nachweisen konnten, dass sich eine Klasse deutlich von den anderen unterscheidet. Der Nachweis von Klassenunterschieden ist eine der schwierigsten und wichtigsten Aufgaben in diesem Bereich.
Der Unterschied zwischen Klassen kann kaum unterscheidbar oder offensichtlich sein, und es ist ziemlich schwierig, alle Klassen gut zu verstehen. Aus diesem Grund haben wir diesen Leitfaden zu den sieben grundlegendsten Schwierigkeitsgraden zusammengestellt. Und ja, Sie werden BPP und BQP nicht länger verwechseln.
P.
Bezeichnet : Polynomzeit
Kurzbeschreibung : Alle Aufgaben, die ein klassischer (Nicht-Quanten-) Computer leicht lösen kann.
Genaue Beschreibung : Algorithmen der Klasse P sollten nicht mehr funktionieren und die richtige Antwort nicht mehr als in der Zeit n
c geben , wobei n die Länge der Eingabedaten ist und c eine Konstante ist.
Typische Aufgaben :
- Ist die Zahl eine Primzahl?
- Was ist der kürzeste Weg zwischen zwei Punkten?
Was Forscher gerne wissen würden : Stimmt P mit NP überein? Zufall würde die Informatik revolutionieren und die meisten kryptografischen Systeme bedeutungslos machen (aber fast niemand glaubt dies).
NP
Bezeichnet : nicht deterministische Polynomzeit
Kurzbeschreibung : Alle Aufgaben, die ein klassischer Computer leicht überprüfen kann, ob es eine Lösung gibt.
Genaue Beschreibung : Das Problem fällt in die Klasse NP, wenn bei einer Antwort mit Ja ein kurzer Beweis für die Richtigkeit der Antwort vorliegt. Wenn die Eingabe eine Zeichenfolge X ist und Sie entscheiden müssen, ob die Antwort mit "Ja" übereinstimmt, ist ein kurzer Beweis eine andere Zeichenfolge, Y, mit der die korrekte Antwort "Ja" in Polynomzeit überprüft werden kann. (Y wird manchmal als „Kurzzeuge“ bezeichnet - alle Aufgaben von NP haben Kurzzeugen, dank derer sie überprüft werden können).
Typische Aufgaben :
- Die Aufgabe des Klickens . Stellen Sie sich ein Diagramm mit Kanten und Scheitelpunkten vor. Die Scheitelpunkte geben beispielsweise Benutzer des sozialen Netzwerks an, und die Kante bedeutet, dass sie „Freunde“ sind. Eine Clique ist eine Teilmenge dieses Diagramms, in der alle Menschen miteinander befreundet sind. Sie können die folgenden Fragen zum Diagramm stellen: Befindet sich ein Klick von 20 Personen darin? 50 Leute? 100? Das Finden einer Clique ist eine NP-vollständige Aufgabe , dh ihre Komplexität ist die höchste aller NP-Aufgaben. Eine mögliche Antwort - eine Teilmenge von 50 Knoten, die ein Klick sein kann oder nicht - ist jedoch leicht zu überprüfen.
- Die Aufgabe des Verkäufers . Gibt es bei einer Reihe von Städten mit Entfernungen zwischen zwei Paaren eine Möglichkeit, alle Städte zu umgehen und weniger als eine bestimmte Entfernung zu fahren? Kann ein Verkäufer beispielsweise alle US-Hauptstädte mit weniger als 18.000 km bereisen?
Was Forscher gerne wissen würden: P = NP? Spezialisten für Informatik und kamen diesem Problem nicht nahe.
PH
Bezeichnet : Polynomhierarchie
Kurzbeschreibung : PH ist eine Verallgemeinerung von NP. Es enthält alle Aufgaben, die Sie erhalten können, indem Sie mit einer Aufgabe von NP beginnen und zusätzliche Schwierigkeitsgrade festlegen.
Genaue Beschreibung : PH enthält Aufgaben mit einer Reihe verschiedener „Quantifizierer“, die diese Aufgaben komplizieren. Ein Beispiel für ein Problem mit verschiedenen Quantifizierern: Wenn wir X erhalten, gibt es Y, so dass für jedes Z W existiert, für das R erfüllt ist? Je mehr Quantifizierer das Problem enthält, desto komplizierter ist es und desto höher ist die Polynomhierarchie.
Eine typische Aufgabe besteht darin, festzustellen, ob es wirklich einen Klick der Größe 50 gibt und keinen Klick der Größe 51.
Was die Forscher gerne wissen würden : Noch konnte niemand nachweisen, dass sich PH von P unterscheidet. Dieses Problem entspricht der Gleichheit von P und NP, denn wenn sich plötzlich herausstellt, dass P = NP ist, werden alle PHs auf P (P = PH) reduziert.
PSPACE
Bezeichnet : Polynomraumbeschränkung
Kurzbeschreibung : PSPACE enthält alle Aufgaben, die mit einer angemessenen Menge an Speicher gelöst werden können.
Genaue Beschreibung : Bei der Lösung von PSPACE-Aufgaben sorgen Sie sich nicht mehr um die Zeit, sondern nur um die Speicherkapazität, die für die Funktionsweise des Algorithmus erforderlich ist. Informatiker haben bewiesen, dass PSPACE einen PH enthält, der NP enthält, das P enthält.
Typische Aufgabe : Alle Aufgaben von P, NP und PH sind in PSPACE enthalten.
Was Forscher gerne wissen würden : Unterscheidet sich PSPACE von P?
Bqp
Bezeichnet : Quantenpolynomzeit mit Fehlerwahrscheinlichkeitsbegrenzung
Kurzbeschreibung : Alle Aufgaben, die auf einem Quantencomputer leicht gelöst werden können.
Genaue Beschreibung : Alle Aufgaben, die auf einem Quantencomputer in Polynomzeit gelöst werden können.
Typisches Problem : Finden Sie Primfaktoren einer ganzen Zahl.
Was Forscher gerne wissen würden : Bisher wurde nachgewiesen, dass BQP in PSPACE enthalten ist und dass BQP P enthält. Forscher wissen nicht, ob BQP in NP enthalten ist, aber sie glauben, dass diese beiden Klassen nicht verglichen werden können - es gibt Aufgaben, die Teil von NP sind. aber nicht in BQP und umgekehrt.
EXPTIME
Bezeichnet : exponentielle Zeit
Kurzbeschreibung : Alle Aufgaben, die auf einem klassischen Computer in exponentieller Zeit gelöst werden können.
Genaue Beschreibung : EXP enthält alle vorherigen Klassen - P, NP, PH, PSPACE und BQP. Die Forscher haben bewiesen, dass es sich von P unterscheidet - sie haben Aufgaben entdeckt, die Teil von EXP und nicht Teil von P sind.
Typische Aufgabe : Verallgemeinerung von Spielen wie Schach und Dame. Wenn ein Schachbrett eine beliebige Größe haben kann, wird die Aufgabe, festzustellen, ob einer der Spieler einen Vorteil hat, zur Aufgabe von EXP.
Was Forscher gerne wissen würden : Sie möchten beweisen, dass PSPACE kein EXP enthält. Sie glauben, dass es Aufgaben gibt, die Teil von EXP, aber nicht Teil von PSPACE sind, da das Lösen einer Aufgabe von EXP manchmal viel Zeit in Anspruch nimmt. Forscher wissen, wie man EXP und P trennt.
BPP
Bezeichnet : Polynomzeit mit Fehlerwahrscheinlichkeitsbegrenzung
Kurzbeschreibung : Aufgaben, die mit zufälligen Algorithmen schnell gelöst werden können.
Genaue Beschreibung : BPP ist dasselbe wie P, mit dem Unterschied, dass der Algorithmus Schritte enthalten kann, in denen Entscheidungen zufällig getroffen werden. Algorithmen in BPP müssen die richtigen Antworten mit einer Wahrscheinlichkeit nahe 1 geben.
Typische Aufgabe : Sie haben zwei verschiedene Formeln, die Polynome mit vielen Variablen angeben. Berechnen diese Formeln das gleiche Polynom? Dies ist die Aufgabe der Überprüfung der Polynomidentität.
Was Forscher gerne wissen würden : Sind BPP und P gleich? Wenn sie gleich sind, könnte jeder Algorithmus mit Zufälligkeit aus der Zufälligkeit eliminiert werden. Sie glauben, dass es so ist - dass es für jedes Problem, für das es einen effektiven Zufallsalgorithmus gibt, einen effektiven deterministischen Algorithmus gibt -, aber sie konnten dies noch nicht beweisen.