NP-schwere Probleme: Überblick

Der Abschnitt beginnt mit der Einführung verschiedener NP-schwieriger Probleme aus der kombinatorischen Optimierung. Es werden konkrete Beispiele wie das 0/1-Knapsack Problem (Problem 5.1), das Traveling Salesman Problem (TSP, Problem 5.2), das Maximum Cut Problem (Problem 5.3) und das Quadratic Assignment Problem (QAP, Problem 5.5) genannt und jeweils die Problemstellung sowie die Instanzbeschreibung definiert. Weiterhin werden das Maximum Clique Problem (Problem 5.7), das Bin Packing Problem (Problem 5.9), das Survivable Network Design Problem (Problem 5.11), das Facility Location Problem (Problem 5.12) und das parallele Maschinen-Scheduling Problem (Makespan-Minimierung, Problem 5.13) vorgestellt. Ein zentraler Punkt ist die gemeinsame Eigenschaft dieser Probleme: Es ist derzeit unbekannt, ob polynomiale Algorithmen für diese existieren, was ihre hohe Komplexität unterstreicht. Die Frage nach der Existenz von Algorithmen mit polynomial beschränkter Laufzeit wird explizit angesprochen, wobei die Wahrscheinlichkeit für deren Existenz als gering eingeschätzt wird. Der Begriff der 'polynomialen Beschränktheit' der Laufzeit wird präzisiert und die Bedeutung der Eingabelänge für die Komplexitätsanalyse hervorgehoben. Die Schwierigkeit der Probleme wird durch die fehlende Kenntnis von polynomialen Algorithmen und der unwahrscheinlichen Existenz eines starken Dualitätstheorems für diese untermauert.

Für jedes der genannten NP-schwierigen Probleme wird eine präzise formale Beschreibung der Instanz und der Aufgabenstellung geliefert. Dies beinhaltet die Definition der Eingabeparameter (z.B. Gewichte und Werte beim Rucksackproblem, Kantenlängen beim TSP, Kantengewichte beim Maximum Cut Problem, Kostenmatrizen bei quadratischen Optimierungsproblemen). Die Aufgabenstellung wird als Optimierungsproblem formuliert (z.B. Minimierung der Kosten, Maximierung des Gewinns, Finden einer optimalen Zuordnung). Die formale Beschreibung dient als Grundlage für die spätere Analyse der Komplexität der Probleme. Die Instanzen sind jeweils so definiert, dass sie eine präzise mathematische Darstellung der Probleme ermöglichen. Diese formale Beschreibung ist essenziell für die spätere Einordnung in Komplexitätsklassen und die Diskussion der algorithmischen Lösbarkeit. Die Verwendung von Mengennotation und mathematischer Symbolik (z.B. ∈, ⊆, ∑) unterstreicht den mathematisch präzisen Charakter der Problemdefinitionen. Die detaillierte Beschreibung der Instanzen ermöglicht es, die Probleme einheitlich zu behandeln und die Komplexitätsuntersuchungen fundiert durchzuführen.

Der Abschnitt verdeutlicht den engen Zusammenhang zwischen Optimierungsproblemen und Entscheidungsproblemen. Zu jedem Optimierungsproblem (Minimierung oder Maximierung) wird ein zugehöriges Entscheidungsproblem definiert, das die Frage nach der Existenz einer Lösung mit einem bestimmten Schwellenwert (α) beantwortet. Beispielsweise wird die Frage, ob es für einen gegebenen Graphen einen Hamilton-Kreis mit Kosten ≤ α gibt, als Entscheidungsproblem zum Traveling Salesman Problem formuliert. Es wird hervorgehoben, dass die polynomiale Lösbarkeit eines Optimierungsproblems auch die polynomiale Lösbarkeit des zugehörigen Entscheidungsproblems impliziert. Dieser Zusammenhang ist wichtig, da die Komplexität von Entscheidungsproblemen leichter analysiert werden kann und diese oft als Grundlage für die Klassifizierung von Optimierungsproblemen dienen. Die Formulierung von Entscheidungsproblemen vereinfacht die Komplexitätsanalyse, da sie auf die Frage nach der Existenz einer Lösung reduziert werden, und nicht auf die Suche nach der optimalen Lösung. Die Umformulierung von Optimierungsproblemen in Entscheidungsprobleme ist ein wichtiges Werkzeug der Komplexitätstheorie.

Dieser Abschnitt betont den Unterschied und die Beziehung zwischen Optimierungsproblemen und Entscheidungsproblemen. Jedes Optimierungsproblem (Minimierung oder Maximierung) lässt sich in ein äquivalentes Entscheidungsproblem umformulieren. Ein Entscheidungsproblem stellt eine Ja/Nein-Frage, beispielsweise ob eine Lösung mit einem Zielfunktionswert mindestens oder höchstens α existiert, wobei α Teil der Eingabe ist. Ein Beispiel hierfür ist die Frage, ob ein vollständiger Graph einen Hamilton-Kreis mit Kosten ≤ α besitzt. Die Lösbarkeit eines kombinatorischen Optimierungsproblems in polynomialer Zeit impliziert die polynomiale Lösbarkeit des zugehörigen Entscheidungsproblems. Diese Reduktion ist ein wichtiges Konzept zur Klassifizierung und Analyse der Komplexität von Optimierungsproblemen. Die Fokussierung auf Entscheidungsprobleme vereinfacht die Komplexitätsanalyse, da die Suche nach der optimalen Lösung durch die Frage nach der Existenz einer Lösung mit bestimmten Eigenschaften ersetzt wird. Dies bildet eine Brücke zur formalen Definition von Komplexitätsklassen.

Der Text präsentiert mehrere konkrete Beispiele für Entscheidungsprobleme: Das Perfekte Matching Problem (Problem 5.14), das Hamilton-Kreis Problem (Problem 5.15), das Graphenzusammenhangsproblem (Problem 5.16), das Primzahlproblem (Problem 5.17), das Erfüllbarkeitsproblem (SAT, Problem 5.18) und das Problem der LP-Zulässigkeit (Problem 5.19). Für jedes Problem wird die Instanz und die zu beantwortende Ja/Nein-Frage präzise formuliert. Diese Beispiele illustrieren die Vielfalt der Entscheidungsprobleme und ihre unterschiedlichen Anwendungskontexte. Die Probleme repräsentieren unterschiedliche Bereiche der Mathematik und Informatik, von Graphentheorie (Matching, Hamilton-Kreis, Zusammenhang) über Zahlentheorie (Primzahlen) bis hin zur Logik (SAT) und linearen Programmierung (LP-Zulässigkeit). Die klare Definition der Instanzen und Fragen dient dazu, das Verständnis für die unterschiedlichen Typen von Entscheidungsproblemen zu schärfen und die spätere Einordnung in Komplexitätsklassen vorzubereiten.

Der zentrale Teil des Abschnitts behandelt die Komplexitätsklassen P, NP und coNP. Die Klasse P enthält alle Entscheidungsprobleme, die in polynomialer Zeit lösbar sind. NP umfasst Entscheidungsprobleme, für die eine positive Antwort mit Hilfe eines Zertifikats in polynomialer Zeit verifiziert werden kann. coNP beinhaltet Probleme, für die eine negative Antwort in polynomialer Zeit verifizierbar ist. Die Klasse EXP beinhaltet Entscheidungsprobleme, die in exponentieller Zeit lösbar sind. Die Beziehung P ⊆ NP ∩ coNP wird erläutert: Wenn ein Problem in P liegt, ist es auch in NP und coNP, da ein Zertifikat nicht benötigt wird, wenn die Lösung in polynomialer Zeit gefunden werden kann. Die Bedeutung der Zertifikate wird im Kontext von NP und coNP hervorgehoben: Sie dienen als Beweise für positive (NP) bzw. negative (coNP) Antworten. Der Abschnitt liefert ein grundlegendes Verständnis der wichtigsten Komplexitätsklassen und ihrer Beziehungen, welche essentiell sind um die Komplexität der zuvor eingeführten Entscheidungsprobleme einzuschätzen. Die Frage P=NP, ein ungelöstes Hauptproblem der Informatik, wird implizit angesprochen.

Dieser Abschnitt legt den mathematischen Rahmen für die Beschreibung von Entscheidungsproblemen fest. Entscheidungsprobleme werden als Teilmengen Π eines Alphabets Σ* (Menge aller endlichen Folgen über Σ) definiert, wobei Σ typischerweise {0, 1} ist. Die Länge eines Wortes x in Σ* wird mit |x| bezeichnet. Das Hamilton-Kreis-Problem wird als Beispiel verwendet, um zu zeigen, wie eine Menge von Graphen mit Hilfe einer injektiven Abbildung (Kodierung) κ in Σ* abgebildet werden kann, z.B. durch Binärdarstellung von Adjazenzlisten. Die formale Definition von Entscheidungsproblemen als Sprachen über einem Alphabet bildet die Grundlage für die präzise Analyse ihrer Komplexität. Die Verwendung eines formalen Modells erlaubt es, die Komplexität unabhängig von konkreten Implementierungen zu untersuchen. Die Kodierung von Problemen in binärer Form ist essentiell für die Messung der Eingabelänge und die Definition von polynomialer Zeit.

Ein Algorithmus wird als endliche Menge A von geordneten Paaren (uᵢ, uᵢ₀) ⊆ Σ* × Σ* definiert. Die vom Algorithmus A akzeptierte Sprache ist L_A = {w ∈ Σ* | A akzeptiert w}. Ein Algorithmus löst ein Entscheidungsproblem Π in polynomialer Zeit, wenn L_A = Π ist und Konstanten C, k ∈ {1, 2, ...} existieren, so dass für jedes w ∈ Π die vom Algorithmus erzeugte Folge höchstens C · |w|^k Glieder hat. Dieses Algorithmenmodell, obwohl vereinfacht, ist (bis auf polynomiale Laufzeitfaktoren) äquivalent zum Turing-Maschinen-Modell. Die Definition der polynomialen Laufzeit ist zentral für die Klassifizierung von Problemen in die Komplexitätsklasse P. Die Bedingung, dass die Länge der vom Algorithmus generierten Folge durch ein Polynom in der Eingabelänge beschränkt ist, präzisiert den Begriff der Effizienz. Das gewählte Modell ermöglicht die formale Analyse der Laufzeit und die Abgrenzung zwischen effizienten (polynomialen) und ineffizienten (z.B. exponentiellen) Algorithmen.

Die Komplexitätsklassen P, NP und coNP werden formal definiert. P enthält alle Π ⊆ Σ*, für die ein Algorithmus A existiert, der Π in polynomialer Zeit löst. NP enthält alle Π ⊆ Σ*, für die ein Π₀ ∈ P und Konstanten C, k existieren, so dass für jedes w ∈ Σ* gilt: w ∈ Π ⇔ ∃z ∈ Σ*: |z| = C · |w|^k, wz ∈ Π₀. coNP enthält alle Π ⊆ Σ*, für die ein Π₀ ∈ P und Konstanten C, k existieren, so dass für jedes w ∈ Σ* gilt: w ∈ Π ⇔ ∀z ∈ Σ*: |z| ≤ C · |w|^k, wz ∈ Π₀. Diese Definitionen formalisieren die intuitiven Vorstellungen von polynomialer Lösbarkeit (P), polynomialer Verifizierbarkeit positiver Antworten (NP) und polynomialer Verifizierbarkeit negativer Antworten (coNP). Die Verwendung von Quantoren (∃ und ∀) und der Bedingung an die Länge des Zertifikats z sind zentral für das Verständnis der Unterschiede zwischen diesen Klassen. Diese formalen Definitionen bilden die Grundlage für die theoretische Analyse der Komplexität von Algorithmen und Entscheidungsproblemen.