Entscheidungsprobleme und Komplexitätsklassen

 Wir betrachten Fragen des folgenden Typs:

Sind die Graphen G₁ und G₂ isomorph ?

Hat G eine Komponente mit genau 5 Ecken ?

Besitzt G eine Brücke ? Ist G Eulersch? Ist G Hamiltonsch ?

 Diese Fragen gehören als ja-nein-Fragen zur Klasse der sog. Entscheidungsprobleme (die auch Fragen anderer mathematischer Gebiete umfasst). Wie wir im Fall der Existenz einen Isomorphismus, eine Komponente der Ordnung 5, eine Brücke, einen Euler-Zug oder einen Hamilton-Kreis finden, ist eine andere Frage, ein sog. Konstruktionsproblem. Beide Probleme hängen, wie wir am Beispiel der Euler-Züge gesehen haben, eng zusammen. Im Folgenden betrachten wir nur Entscheidungsprobleme.

 Formal ist ein Entscheidungsproblem eine Funktion D : I → { 0, 1 }. Dabei ist I eine Menge von sog. Inputs und die Funktionswerte 1 und 0 der Funktion D stehen für „ja“ bzw. „nein“. Die Frage, ob zwei Graphen mit Ecken in ℕ isomorph sind, wird als Entscheidungsproblem D : I → { 0, 1 } mit

I  =  { (G₁, G₂) | G₁, G₂ sind Graphen mit Ecken in ℕ },

D(G₁, G₂) = 1  genau dann, wenn  G₁ ≅ G₂

formalisiert.

 Für ein Entscheidungsproblem D : I → { 0, 1 } stellt sich die Frage nach der algorithmischen Berechenbarkeit: Gibt es ein Computer-Programm, das für jeden Input i  ∈  I den Wert D(i) in endlich vielen Schritten korrekt berechnet? Wenn ja: Welche Komplexität (Anzahl der Rechenschritte in Abhängigkeit des Inputs) hat eine solche Berechnung? Ein berechenbares Entscheidungsproblem nennen wir (algorithmisch) lösbar. Viele Probleme können durch ein brute force Verfahren gelöst werden. Wir können zum Beispiel alle möglichen Kantenzüge der Länge |E| + 1 eines Graphen G = (E, K) auflisten und jeden Kantenzug überprüfen, ob er ein Hamilton-Kreis ist oder nicht. Finden wir einen Hamilton-Kreis, so geben wir 1 aus, andernfalls 0. Derartige Verfahren sind theoretisch uninteressant und aufgrund ihres Rechenaufwands in der Praxis zumeist gar nicht durchführbar. Es stellt sich also die Frage nach der Existenz von Algorithmen einer in einem bestimmten Sinne „guten“ Komplexität. Drei prominente Klassen von Entscheidungsproblemen mit einer guten Komplexität sind die Komplexitätsklassen P, NP und co-NP:

 Die Klasse P besteht aus allen Entscheidungsproblemen, die sich, gemessen an der Länge ℓ des Inputs, in polynomieller Laufzeit lösen lassen. Für ein Problem D : I → { 0, 1 } mit einem Graphen G = (E, K) als Input ist zum Beispiel die natürliche Zahl ℓ(G) = |E| + |K| ein gutes Maß für die Länge eines Inputs. Das Problem D liegt nun in der Klasse P, wenn es einen Algorithmus und ein Polynom p : ℕ → ℕ gibt, sodass der Algorithmus für alle Inputs G  ∈  I die korrekte Antwort D(G)  ∈  { 0, 1 } in höchstens p(ℓ(G)) vielen Rechenschritten findet. Je geringer der Grad des Polynoms p ist, desto effizienter ist der Algorithmus. Hat p den Grad k, so sagen wir auch, dass der Algorithmus die Laufzeit O(n^k) besitzt. So hat zum Beispiel der Algorithmus von Hierholzer bei geeigneter Implementierung eine lineare Laufzeit (Grad 1). Die Klasse P ist damit unterteilt in lineare Probleme, quadratische Probleme, Probleme in O(n³) usw. Darüber hinaus sind auch noch Laufzeiten wie O(n log(n)) von Interesse, die zwischen O(n) und O(n²) liegen: Für jeden Input i wird hier das Ergebnis in höchstens c n log(n) + c₀ vielen Schritten gefunden, mit gewissen Konstanten c und c₀. Für die Frage, ob ein Problem in P liegt, spielen diese für die Praxis sehr wichtigen Unterteilungen keine Rolle. Es genügt, wenn irgendein polynomieller Algorithmus existiert.

 Die Klasse NP besteht aus all denjenigen Entscheidungsproblemen, für die im Fall der Existenz eine Lösung in polynomieller Zeit auf ihre Richtigkeit hin überprüft werden kann. Griffiger formuliert:

Geratene Lösungen können polynomiell verifiziert werden.

Formaler liegt ein Problem D : I → { 0, 1 } genau dann in der Klasse NP, wenn es ein Problem D′ : I × J → { 0, 1 } gibt mit:

 Das Hamilton-Problem − die Frage, ob ein gegebener Graph G Hamiltonsch ist oder nicht − gehört zum Beispiel der Klasse NP an. Denn ist der Graph G Hamiltonsch und C ein Hamilton-Kreis in G, so können wir C polynomiell und genauer sogar linear als Hamilton-Kreis verifizieren (mit Hilfe eines Algorithmus mit Input (G, C)). Analog besteht die Klasse co-NP aus denjenigen Entscheidungsproblemen, für die eine negative Lösung in polynomieller Zeit verifiziert werden kann. Anders formuliert: Ein Problem D : I → { 0, 1 } ist genau dann in co-NP, wenn das komplementäre Problem D^c : I → { 0, 1 } mit D^c(i) = 1 − D(i) für alle i  ∈  I in NP liegt. Beispielsweise liegt das Problem „Ist der Graph nicht Hamiltonsch?“ in co-NP.

 Die Abkürzung NP steht nicht etwa für nicht-polynomiell, sondern für non-deterministic polynomial. Diese Bezeichnung geht auf eine äquivalente Definition der Klasse NP zurück, bei der nichtdeterministische Algorithmen zur Problemlösung verwendet werden.

 Es gilt P ⊆ NP. Die Umkehrung ist ein offenes Problem:

 Das P ≠ NP-Problem gehört zu den sieben Millenniums-Problemen der Mathematik, die mit Ruhm und Ehre und zudem einem hohen Preisgeld verbunden sind. Ebenso offen ist:

 Viele Mathematiker nehmen an, dass P ≠ NP und NP ≠ co-NP. Es gilt

NP  ≠  co-NP  impliziert  P  ≠  NP.

Dagegen ist P ≠ NP und NP = co-NP nach dem jetzigen Wissensstand nicht auszuschließen. Es gilt P ⊆ NP ∩ co-NP. Ob die Inklusion echt ist, ist offen.

Das Hamilton-Problem und NP-Vollständigkeit

 Das Hamilton-Problem liegt „wahrscheinlich“ nicht in P. Wie können wir diese Aussage, die zum Typ Expertenvermutung gehört, rechtfertigen? Zum einen ist kein polynomieller Algorithmus für das Hamilton-Problem bekannt. Das ist keine wirklich gute Begründung. Wesentlich gehaltvoller ist eine ganz andersartige Argumentation, die eine weitere Komplexitätsklasse ins Spiel bringt:

 Ein Entscheidungsproblem D* : I* → { 0, 1 } in NP heißt NP-vollständig, wenn sich jedes Problem D : I → { 0, 1 } in NP in polynomieller Zeit auf das Problem D* reduzieren lässt. Dies bedeutet genauer, dass wir für jedes D : I → { 0, 1 } in NP in polynomieller Zeit jedem Input i  ∈  I einen Input i*  ∈  I* zuordnen können derart, dass D(i) = D*(i*) für alle i  ∈  I. Jedes Problem D in NP kann also in das Problem D* übersetzt werden (mit polynomiellem Aufwand). Anschaulich sind die NP-vollständigen Probleme die schwierigsten Probleme in NP. Nach Definition gilt:

Solange die Frage P ≠ NP offen ist, ist der Nachweis der NP-Vollständigkeit eines Problems das beste Mittel, um zu begründen, dass ein Entscheidungsproblem „wahrscheinlich“ nicht in P liegt. Für das Hamilton-Problem und zahlreiche weitere Probleme ist ein solcher Nachweis möglich. Richard Karp hat 1972 bewiesen, dass das Hamilton-Problem NP-vollständig ist. Damit würde ein polynomieller Algorithmus, der einen beliebigen Graphen korrekt auf die Eigenschaft „Hamiltonsch“ überprüft, P = NP implizieren. „Wahrscheinlich“ gibt es also keinen solchen Algorithmus.

Das Isomorphie-Problem

 Eine besondere Stellung nimmt das Isomorphie-Problem ein, das die Frage stellt, ob zwei gegebene Graphen isomorph sind oder nicht. Dieses Problem liegt in NP, denn für zwei isomorphe Graphen G₁ und G₂ können wir einen Isomorphismus f : E₁ → E₂ in polynomieller Zeit als solchen erkennen. Im Gegensatz zum Hamilton-Problem und vielen anderen NP-Problemen, für die kein polynomieller Algorithmus gefunden werden konnte, ist es nicht gelungen zu zeigen, dass das Isomorphie-Problem NP-vollständig ist. Zudem hat die Hypothese, dass das Isomorphie-Problem in P liegt, ungewöhnliche komplexitätstheoretische Konsequenzen. Vermutlich ist das Isomorphie-Problem also ein Problem in NP, das weder in P liegt noch NP-vollständig ist.

Das Halte-Problem

 Zum Abschluss möchten wir noch kurz ein Entscheidungsproblem ansprechen, das für die Geschichte der Mathematik und die Entwicklung der Computer eine fundamentale Rolle gespielt hat. Eine Formulierung ist:

 Das Halte-Problem ist ein Entscheidungsproblem D : I → { 0, 1 }, wobei die Inputs i  ∈  I Paare der Form (Q, q) sind, mit einem Programm Q und einem zugehörigen Input q. Alan Turing zeigte 1936 mit Hilfe der heute nach ihm benannten Turing-Maschinen, dass das Halte-Problem unlösbar ist. Insbesondere ist das Halteproblem nicht in NP. Es gehört der Klasse der NP-schweren Probleme an, also der Probleme D*, auf die sich alle Probleme in NP in polynomieller Zeit reduzieren lassen. Die NP-vollständigen Probleme sind genau die Probleme, die NP-schwer sind und zudem in NP liegen.

 Insgesamt ergibt sich folgendes Bild: