Einführung in NP-harte Probleme

Bisher ausgewählte Probleme für die (sehr) effiziente Algorithmen existieren (Selection Bias).

• Binary Search $O(\log n)$
• MergeSort $O(n\log n)$
• Sequence alignment $O(nm)$
• (Direct) Matrix Multiplication $O(n^3)$
• $\dots$

Aber es gibt auch viele Probleme, für die es (noch?) keine effizienten Algorithmen gibt.

MST vs TSP

Problem Definition: Minimum Spanning Trees (MST)

Eingabe: Ein verbundener ungerichteter Graph $G = (V, E)$ und (reel-wertige) Kosten $c_e$ für jede Kante $e\in E$

Ausgabe: Ein aufspannender Baum (spanning tree) $T \subseteq E$ von $G$ mit minimaler Summe $\sum_{e\in T} c_e$ von Kantenkosten.

Greedy-Algorithmus zur Lösung des MST-Problems

Einfache greedy-Algorithmen lösen das MST-Problem effizient:

• Prims Algorithmus
• Kruskals Algorithmus

Beispiel:

Prim-Algorithmus

Eingabe: Ein verbundener ungerichteter Graph $G = (V, E)$ und (reel-wertige) Kosten $c_e$ für jede Kante $e\in E$

Ausgabe: Die Kanten eines aufspannender Baum (spanning tree) $T \subseteq E$ von $G$ mit minimaler Summe.

---

// Initialization
$X:= \{s\}$ // s is an arbitrarily chosen vertex
$T := \emptyset $ \\ invariant: the edges in $T$ span $X$
// Main loop
while there is an edge $(v, w)$ with $v \in X, w \notin X$ do
  $(a, b) :=$ a minimum-cost such edge
  add verted $b$ to $X$
  add edge $(a,b)$ to $T$
return $T$

Der einfache greedy-Algorithmus liefert (immer) eine optimale Lösung des MST-Problems. Beweis siehe z.B. T. Roughgarden, Algorithms Illuminated, Part 3: Greedy Algorithms and Dynamic Programming

Laufzeit

• Laufzeit des (straightforward) Algorithmus (siehe oben): $O(mn)$ mit $m=|E|$ und $n=|V|$
• Es gibt auch eine Heap-basierte Version mit Laufzeit $O\left((m+n)\log n \right)$

Problem Definition: Traveling Salesman Problem (TSP)

Eingabe: Ein vollständig-verbundener ungerichteter Graph $G = (V, E)$ und (reel-wertige) Kosten $c_e$ für jede Kante $e\in E$

Ausgabe: Eine Tour $T \subseteq E$ von $G$ mit minimaler Summe $\sum_{e\in T} c_e$ von Kantenkosten.

Eine Tour ist ein Zyklus, der jeden Knoten exakt-einmal besucht.

Quiz

Wieviele unterschiedliche Touren gibt es?

Eigenschaften des TSP-Problems

• Anzahl der unterschiedlichen Touren: $\frac{1}{2}(n-1)!$
• kein effizierter (polynominaler) Algorithmus für den TSP bisher entwickelt.
• Spekulation: Es gibt keinen effizierten (polynominalen) Algorithmus zur Lösung des TSP-Problems. E gibt aber bisher keinen mathematischer Beweis, dass ein polynominaler Algorithmus nicht existieren kann.

Anwendungen

Anwendungen, bei denen verschiedene Aufgaben hintereinander ausgeführt werden sollen. Dabei hängen die Kosten einer Aufgabe von der vorherigen Aufgabe ab, z.B. Minimierung der Umkonfigurierungskosten einer Auto-Fabrik, in der verschiedene Auto-Typen hergestellt werden sollen.

MST vs TSP

• Der verbundene Graph beim MST Problem kann auch leicht in einen komplett-verbundenen Graphen ungewandelt werden, z.B. durch Hinzufügen von Kanten mit sehr hohen Kosten. Das macht nicht den Unterschied.
• TSP kann in ein TSPP (traveling salesman path problem) umgewandelt werden. Im TSPP soll jeder Knoten genau einmal besucht werden (ohne Zyklus). D.h. der Zyklus macht nicht den Unterschied.

Einfache und harte Probleme

• Praktische-anwendbare Probleme: Sogenannte einfache (easy) oder praktisch-anwendbare (tractable) Probleme können durch Computeralgorithmen gelöst werden, die in polynomieller Zeit ablaufen.
• Harte Probleme: Nicht in polynominaler Zeit lösbar, z.B. in exponentialer Laufzeit.

Definition: In polynominaler Zeit lösbare Probleme (polynominal-time solvable problems)

Ein berechenbares Problem ist in polynominaler Zeit lösbar, wenn es einen Algorithmus gibt, der für jede Eingabe eine korrekte Ausgabe in polynominaler Zeit findet.

• D.h. die Laufzeit ist im schlechtesten Fall $O(n^d)$.
• Hier bezeichnen wir solche Probleme als einfach (easy) bzw. praktisch-anwendbar (tractable). Unabhängig, ob diese Probleme/Algorithmen wirklich in der Praxis sinnvoll einsetzbar sind (z.B. $n^{100}$).
• Ein solches Problem ist in der Klasse $P$

Skalierung der Laufzeit für polynominale Probleme

Bei festem Zeitbudget, skalieren die Eingabemenge $n$ bei einer Verdopplung der Rechenresourcen mit einem festen Faktor, d.h. der Faktor ist unabhängig von $n$.

Hinweis: Die Verdopplung der Rechenresourcen ist äquivalent zu Halbierung der Konstante $C$.

Beispiele:

• $O(n^2): t = Cn^2$:
• aus $C n^2 = \frac{C}{2} (n')^2$ folgt $n' = \sqrt{2}n \approx 1.414 n$

d.h. bei $O(n^2)$ skaliert die Eingabemenge mit $1.414$ bei Verdopplung der Rechenresourcen.

analog

• $O(n)$: $n' = 2n$
• $O(n^3)$: $n' = \sqrt[3]{2}n \approx 1.26 n$

Vergleich: Polynominal vs. exponentiell

p_vs_np()

Evidenz für harte Probleme

• schwache Evidenz: Hunderte brilliante Geister haben bisher (mehrere Jahrzehnte) noch keinen polynominalen (tractable) Algorithmus für das TSP gefunden.
• starke Evidenz: Ein polynominaler Algorithmus für TSP würde auch viele weitere harte Probleme polynominal lösen (durch Reduktion - siehe unten).

Definition NP: In polynominaler Zeit überprüfbare Probleme

Wenn die Lösung eines berechenbares Problem in polynominaler Zeit überprüfbar ist, dann ist das Problem in NP (non-deterministic polynominal).

Dies ist äquivalent dazu, dass ein Problem von einer nicht-deterministischen Turing-Maschine in polynominaler Laufzeit gelöst werden kann. Daher nicht-deterministisch polynominal (NP) lösbar.

Beispiel:

• Soduko

NP-harte Probleme

Informale Beschreibung:

Ein Problem ist NP-hart, wenn es wenigstens genauso-schwierig ist, wie jedes Problem in $NP$ , d.h. jedes Problem mit einfach zu bestätigender Lösung.

Die P $\neq$ NP Vermutung (informal)

Die Überprüfung einer vermeintlichen Lösung eines Problems kann fundamental einfacher sein, als die Lösung zu finden.

NP-harte Probleme (provisorische Definition)

Ein berechenbares Problem ist NP-hart, wenn die Entwicklung eines polynominalen Algorithmus für dieses die P $\neq$ NP Vermutung wiederlegen würde.

Falls die P $\neq$ NP Vermutung gilt für die Komplexitätsklassen:

Algorithmische Strategien für NP-harte Probleme

Folgendes gilt, falls die P $\neq$ NP Vermutung wahr ist:

Drei Eigenschaften, die nicht gleichzeitig für Algorithmen NP-harter Probleme erfüllt sein können

1. Allgemeingültig (general-purpose)
2. Korrekt (correct)
3. Schnell (fast)

Kompromisse bzgl. der Allgemeingültigkeit

Beispiel Weighted-Independent Set Problem (MWIS):

• für die Spezialfälle Pfad-Graphen und azyklische Graphen gibt es effiziente dynamische Programmieralgorithmen. Für den allgemeinen Fall nicht.

Kompromisse bzgl. der Korrektheit

Heuristische Algorithmen

1. Korrektheit bei den meisten Eingaben.
2. "almost correct", z.B. durch Approximationsalgorithmen, z.B. für Optimierungssprobleme (wie TSP): Local Search, Simulated Annealing, Evolutionäre Algorithmen

Kompromisse bzgl. der worst-case Laufzeit

• Schnell für viele typische Eingabedaten
• Schneller als exhaustive search.

Drei Fakten über NP-harte Probleme

1. Ubiquity: NP-harte Probleme kommen oft in der Praxis vor.
2. Intractability: Es gibt keine allgemeingültigen, korrekten und schnellen Lösungsalgorithmen.
3. Not a death sentence: NP-harte Probleme können oft in der Praxis problemspezifisch (nicht-allgemeingültig) gelöst werden, ggf. approximativ, durch genügend Resourcen und algorithmische Verfeinerung.

Beweis der NP-Hardnesss

Wie kann gezeigt werden, dass ein Problem zur Klasse NP-hart dazugehört.

Reduktion

Definition:

Ein Problem $A$ reduziert sich auf ein Problem $B$, wenn ein Algorithmus, der $B$ löst, sich auch auf das Problem $A$ anwenden (übersetzen) lässt. Ein Subroutine, die $B$ löst, wird dabei nur maximal polynominal oft vom Lösungsalgorithmus für $A$ aufgerufen.

Bespiel:

• Finden des Medians durch Sortierung.
• all pairs shortest path lässt sich auf single source shortest path reduzieren.
• Longest common subsequence lässt sich auf Sequenzalignment reduzieren.

Hinweis: Es kann effizientere Algorithmen zum Lösen des Problems geben, als die Reduktion.

Reduktion erzeugt Tractability

Wenn sich Problem $A$ auf $B$ reduzieren lässt, dann heißt dies, dass die praktische Anwendbarkeit (Tractability) von $B$ die Tractability von $A$ induziert:

• aus der Reduktion $A \rightarrow B$ ($A$ lässt sich mit Hilfe von $B$ lösen) mit $B$ ist tractable
• folgt für die Tractability: $B \rightarrow A$, d.h. wenn $B$ tractable ist, ist auch $A$ tractable.

Reduktion erzeugt Intractability

Wenn sich Problem $A$ auf $B$ reduzieren lässt und $A$ NP-hart ist, dann ist $B$ auch NP-hart:

• aus der Reduktion $A \rightarrow B$ mit $A$ ist intractable
• folgt für die Intractability: $A \rightarrow B$, d.h. wenn $A$ intractable ist, ist auch $B$ intractable.

Zeigen der NP-Hardness eines Problems

Um zu beweisen, dass ein Problem $B$ NP-hart ist:

1. Wähle ein NP-hartes Problem $A$
2. Zeige, dass sich $A$ auf $B$ reduzieren lässt.

Anfängerfehler

1. Denken, dass NP-hart für not-polynominal steht. NP steht für nondeterministic polynominal time (Lösbar in polynominaler Zeit von einer nicht-deterministischen Turing-Maschine).
2. Statt NP-hartes Problem zu sagen, dass das Problem in NP ist bzw. dass es ein NP-Problem ist. $P$-Probleme sind auch in NP, entscheidend ist hier auch das "-hart" (vgl. Abb. oben).
3. NP-harte Probleme sind unproblematisch, da sie im allgemeinen in der Praxis gelöst werden können.
4. Denken, dass Fortschritte in der Computertechnologie (Hardware) uns vor der Problematik NP-harter Probleme in Zukunft erlösen kann. Das Gegenteil ist ehr der Fall (Datenmengen wachsen!)
5. Die Folgerungen von Reduktionen in die falsche Richtung (siehe oben)

Zusammenfassung

• Ein Algorithmus mit polynominale Zeitkomplexität ist ein Algorithmus mit worst-case Laufzeit in $O(n^d)$ mit Eingabegröße $n$ und einer Konstanten $d$.
• Ein berechenbares Problem ist ein polynominaler Zeit lösbar, wenn es einen Algorithmus mit polynominale Zeitkomplexität gibt, der es für alle möglichen Eingaben korrekt löst.
• Die Theorie der NP-Hardness setzt einfache Probleme mit in polynominaler-Zeit lösbare Probleme gleich.
• Unformal sagt die $NP \neq P$ Vermutung aus, dass es einfacher ist eine Lösung zu überprüfen als zu finden. Es gibt Problem bei denen die Lösung zu überprüfen polynominal ist. Für das Finden von diesen Lösungen gibt es aber keine polynominalen Algorithmen.
• Ein Problem ist NP-hart, wenn die Entwicklung eines polynominalen Algorithmus für das Problem die $NP \neq P$ Vermutung widerlegen würde.
• Ein polynominaler Algorithmus für ein $NP$-hartes Problem würde automatisch tausend weitere NP-harte Probleme lösen.
• NP-harte Proble sind in der Praxis allgegenwärtig.
• Um in der Praxis ein NP-hartes Problem anzugehen, müssen Kompromisse bzgl. der Allgemeingültigkeit, Korrektheit oder Geschwindigkeit gemacht werden.
• Schnelle heuristische Algorithmen haben gute Laufzeiten. Sie liefern aber nicht immer korekte Lösungen.

Literatur

• T. Roughgarden, Algorithms Illuminated, Part 4: Algorithms for NP-Hard Problems
  • free access to Chapter 19: What Is NP-Hardness?