Bisherige Herangehensweise an Algorithmen

• aufbauend auf Modell „Registermaschine“
• für Problemstellung (z. B. kürzeste Wege) finde schnelleren Algorithmus
  • Verbesserung z. B. von $\mathcal{𝒪}\left(n^2\right)$ zu $\mathcal{𝒪}\left(nlogm\right)$
  • manchmal nicht erfolgreich: kein schneller Algorithmus für TSP
• theoretischer Ansatz
• $\mathcal{𝒪}$-Notation erlaubt Klassifizierung: $nlogm$ ist besser als $n^2$
  • aber: $n^2$ nicht besser als $10002n^2$

Von hier: 2 Mögliche Richtungen

1. Laufzeiten genauer analysieren.
   • $n^2$ ist besser als $10002n^2$, sogar: $n^3$ ist besser als $100002n^2$ für viele realistische Eingaben!
   • Rechnermodell spezifizieren. Cache-Einfluss, parallele Rechner, etc.
2. Grobere Abschätzung.
   • Was ist überhaupt berechenbar?
   • Ist der Unterschied zwischen TSP und kürzesten Wegen wirklich so signifikant?

Wahl zwischen Praxis und Theorie

• Algorithm Engineering, Big Data
• Berechenbarkeit, Komplexität

Was ist ein Problem?

Eine Fragestellung, die durch Nutzung von Computern korrekt beantwortet werden kann

Genauer:

• zulässige Eingaben des Problems lassen sich eindeutig beschreiben als endliche Folgen über endlichen Alphabeten
• es gibt eine Funktion, die jeder Eingabe die (nicht leere) Menge der korrekten Ergebnisse zuweiset

Einige nicht geeignete Probleme:

• Gerichtsurteile, politische Entscheidungen
• Voraussagen, generierung von Kunst, automatische Übersetzung

Sei $f:N\to R_0^{+}.$

• f heißt polynomiell beschränkt, wenn es ein polynom gibt so dass $f\in O\left(p\right)$
• f wächst superpolynomiell, wenn $f\in \omega \left(n^c\right)$ für alle $c$
• f wächst exponentiell, wenn es ein $𝜀$ gibt mit $f\in \Omega \left({2{}^n}^{𝜀}\right)$
  • offensichtlich: exponentiell impliziert superpolynomiell

wächst superpolynomiell, aber nicht exponentiell

• exponientielles Wachstum ist stark
• aber: ist der Unterschied wirklich so gravierend?
• nur quantitativ oder auch qualitativ?

Beispiel:

• Sei $T$ von uns akzeptierte Rechenzeit
• Rechner mit bestimmter Geschwindigkeit gegeben
• Annahme: $f$ streng monoton wachsend $\Rightarrow$ Umkehrfunktion $f^{-1}$ existiert

Maximale Problemgröße ist dann dann $n:\; =f^{-1}\left(T\right)$

• Rechner nun $k$-mal so schnell
• neue Problemgröße $n^{\ast }:\; =f^{-1}\left(k\cdot T\right)$

Wie verändert sich die Laufzeit?

Exponentielle Laufzeitfunktionen bieten additiv größere Instanzen bei multiplikativ größerer Rechenzeit!

Bisher: Optimierungsprobleme betrachtet

• finde einen kürzesten Weg zwischen zwei Knoten
• berechne einen Huffman-Code
• finde eine kürzeste Tour über alle Knoten eines Graphs

Entscheidungsprobleme:

• nur zwei Antwortmöglichkeiten: ja/nein

Oft: Entscheidungsproblem und Zugehöriges Optimierungsproblem gleich schwer

Eine Reduktion von $A$ auf $B$ ist

• ein Algorithmus (eine Funktion),
• der (die) eine Eingabe für $A$ umwandelt,
• ggf. einen Algorithmus für $B$ benutzt

um $A$ zu lösen.

Dann gilt $A<B$, gelesen: „$A$ nicht schwerer als $B$“

Trivial: Spezialfall auf allgemeines Problem reduzieren

Besonders bedeutsames Ergebnis:

„schweres“ Problem wird reduziert auf „leichtes“

Falls $A<B$ und $B<A$ heißt $A$ und $B$ äquivalent unter Reduktion <

Gegeben Probleme $A$ und $B$

Algorithmus, der $A$ löst ist eine Turing-Reduktion ${<}_T$, wenn

• Rechenzeitvon $A$ ohne Aufruf eines Algorithmus für $B$ polynomiell ist
• Anzahl der Aufrufe eines Algorithmus von $B$ polynomiell beschränkt ist
• die Eingabelänge der Aufrufe von $B$ polynomiell beschränkt ist

Falls es einen polynomiellen Algorithmus für $B$ gibt, ist eine Turing-Reduktion ein polynomieller Algorithmus für $A$

Falls es keinen polynomiellen Algorithmus für $A$ gibt, kann es damit keinen für $B$ geben.

Beispiel: All Pair Shortest Paths durch Single Source Shortest Paths lösen

Einfache Richtung: Entscheidungsvariante ${<}_T$ Optimierungsvariante

• bestimme optimale Lösung
• berechne den Wert der optimalen Lösung
• vergleiche mit gegebenem Wert

Beispiel:

• Optimierungsproblem: kürzeste Wege
• Entscheidungsproblem: gibt es einen kürzesten Weg der Länge maximal $L$?

Komplizierte Richtung: Optimierungsvariante ${<}_T$Entscheidungsvariante

• bestimme obere Schranke OPT
• löse für $L:\; =\frac{OPT}{2}$ Entscheidungsvariante
• bestimme mit binärer Suche den Wert der optimalen Lösung

Vom Wert zur optimalen Lösung:

• prüfe für geeignete Elemente in der Lösung, ob sie den Wert bestimmen
• reduziere Eingabe so lange, bis optimale Lösung rauskommt

Beispiel: kürzeste Wege

• Obere Schranke z. B. ${\sum }_{e\in E}{c}_e$ Summe der Längen
• für jede Kante: wenn man sie entfernt, wird der kürzeste Weg länger?

• soll geeignet sein, formale Beweise zu führen
• möglichst einfach
• Laufzeitverluste sind zu vernachlässigen, solange polynomiell
  • hauptsache Laufzeit ist nicht superpolynomiell

Modell der Wahl: Turingmaschine

Können zeigen:

• gleichmächtig wie Registermaschinen
• Mehrband-Turingmaschinen sind bis auf polynomiellen Faktor gleichmächtig

(erweiterte) Church-Turing-These: Alle Rechnermodelle können sich gegenseitig simulieren (in polynomieller Zeit)

• Erweiterung einer deterministischen Maschine
• statt Übergangsfunktion: Übergangsrelation
• mehrere mögliche Nachfolgezustände
• Nachfolgezustand nicht mehr eindeutig definiert

Vorstellung:

läuft „parallel“ alle möglichen Berechnungspfade ab

Laufzeit: kürzester Pfad zu akzeptierendem Endzustand

• Klasse von Entscheidungsproblemen Nichtdeterministisch Polynomiell

Drei Beschreibungen:

• von einer nichtdeterministischen Turingmaschine in polynomieller Zeit akzeptiert
• es gibt ein polynomielles „Zertifikat“, mit dem eine Lösung überprüft werden kann
• randomisierte Algorithmen mit einseitigem Fehler: ja-Instanzen dürfen abgelehnt werden

NP-Algorithmen können von deterministischen Turingmaschinen in exponentieller Zeit simuliert werden.

• für viele Probleme konnten lange keine polynomiellen Algorithmen gefunden werden
• Vermutung: es gibt Probleme in $NP\setminus P$, d. h. $NP\setminus P\ne \varnothing$
• besondere Reduktion von Entscheidungsproblemen: polynomielle Reduktion ${\le }_P$
  • genau ein Aufruf von $B$-Algorithmus erlaubt
  • dessen Ergebnis muss als Lösung für $A$-Problem genommen werden

NP-Vollständig:

• schwerstes Problem in NP
• alle Probleme in NP können auf NP-vollständige Probleme reduziert werden

Idee:

Viele NP-vollständige Probleme: erhärten Verdacht für $P\ne NP$

3-SAT:

• $n$ Variablen $x_1,x_2,\dots ,x_n\in \left\{0,1\right\}$
• $m$ Klauseln mit genau drei Literalen

SAT ${\le }_P$ 3-SAT

• möglicherweise längere Klauseln in SAT

• füge neue Klauseln $y_i$ hinzu

• spalte Klauseln $x_1\vee x_2\vee x_3\vee \cdots \vee x_k$ auf

• neue Klauseln $x_1\vee x_2\vee y_1$, $\neg y_1,x_3,y_2$, $\neg y_2,x_4,\dots$ auf

Sei eine Instanz lösbar und $x_1\vee x_2\vee x_3\vee \cdots \vee x_k$ eine erüfllte Klausel

• dann ist $x_i=1$ für ein i
• setze $y_j=1$ für links stehende $y_j$
• setze $y_j=0$ für rechts stehende $y_j$

Dann:

• $x_1\vee x_2\vee y_1=1,\neg y_1\vee x_2\vee y_2,\cdots ,\neg y_{i-2}\vee x_{i-1}\vee y_{i-2}=1$ wegen $y_j=1$ für $j<i-1$
• $\neg y_{i-2}\vee x_i\vee y_{i-1}=1$ wegen $x_i$ = 1
• $\neg y_{i-1}\vee x_{i+1}\vee y_i,\cdots \neg y_{k-3}\vee x_{k-1}\vee x_k$ wegen $y_j=0$ für $j\ge i-1$

Jede gültige Variablenbelegung für SAT ist auch gültig für 3-SAT-Instanz

Sei $y_i$, $x_i$ eine gültige Variablenbelegung für die erzeugte 3-SAT-Instanz.

• es können nicht alle 3-Klauseln durch $y$-Literale erfüllt sein.
  • falls alle $y_i=1$, ist eine der letzten beiden $x$-Literale erfllt
  • sonst in der Klausel mit dem ersten $y_i=0$-Literal
• diese $x$-Belegung erfüllt auch die urpsrüngliche Klausel

Jede Lösung für 3-SAT ist auch Lösung für SAT

Betrachte den Spezialfall $c_i=w_i$

• Gewichte entsprechen Nutzen
• Optimierungsproblem: versuche Schranke $B$ möglichst gut zu füllen
• Entscheidungsvariante: gibt es Auswahl der Objekte, so dass Wert/Gewicht genau $B$?

Allgemeiner:

• gegeben $w_i$ für $i=1,\dots ,n$, Gewichtsschranke $B$
• gesucht $S\subseteq 1,2,\dots ,n$ mit ${\sum }_{i\in S}{w}_i=B$

Teilsummenproblem

3-SAT: gegeben $m$ Klauseln $c_1,\dots ,c_m$, $n$ Variablen $x_1,\dots ,x_n$

Idee: Gewicht als Zahl mit $m+n$ Stellen genau zu erreichen

• erste $m$ Ziffern 3: wollen 3 Literale pro Klausel belegen
• folgende $n$ Ziffern: Literal soll entweder mit 1 oder 0 belegt werden

Schwierigkeit:

• für 3-SAT: genügt ein Literal pro Klausel zu erfüllen
  • Lösung: pro Klausel nehme 2 „Füllzahlen“ in Eingabe aufbauen
• Literal kann entweder 0 oder 1 sein
  • Lösung: zwei Zahlen pro Literal in Eingabe, die sich ausschließen

Zahlen $y_i,z_i$ für $i=1,\dots ,n$

• Stelle $m+i$ von $y_i$ und $z_i$ = 1, sonst 0
• $\Rightarrow$ nur eine der beiden Zahlen kann gewählt werden

Klauseln:

• Stelle $j$ von $y_i$ ist 1, wenn $x_i$ positiv in $c_j$ vorkommt
• Stelle $j$ von $z_i$ ist 1, wenn $x_i$ negativ in $c_j$ vorkommt

Sei $S$ gültige Auswahl von $y_i$ und $z_i$-Zahlen:

• ${\sum }_{w\in S}<22\cdots 211\cdots 1$

Für maximum:

• die letzten $n$ Stellen sind genau 1

Jede gültige Auswahl soll sich auf genau aufsummieren

• Stelle $j$ von $x_i$ = 1, wenn $a_i$ in $c_j$ vorkommt
• Stelle $j$ von $y_i$ = 1, wenn $a_i$ in $c_j$ negiert vorkommt

Ermöglicht maximal Beitrag zwei.

• für gültige Lösung muss also eine Eins aus der Variablenbelegung kommen

Laufzeit:

• Konstruktion in $\mathcal{𝒪}\left({\left(n+m\right)}^2\right)$, also polynomiell
• 3-SAT und SSS-Instanzen entsprechen einander
• nur ein Aufruf von SSS-Algorithmus

Impliziert: Rucksackproblem ist auch NP-vollständig

Unterschiede bei Reduktionen

• 3-SAT auf SAT benutzt keine Zahlen
• 3-SAT auf SSS nutzt Zahlen der Länge $m+n$
  • exponentiell groß in $n$ und $m$

Definition:

• sei $max$ die größte Zahl in der Eingabe für ein Problem
• sei $\ell$ die Länge des Problems

Ein Problem heißt Zahlproblem, wenn $max$ nicht durch ein Polynom in $\ell$ beschränkt werden kann.

• Rucksackproblem

• TSP

• nicht aber SAT und 3-SAT

Dynamische Programme

• für Rucksackproblem: Laufzeit $\mathcal{𝒪}\left(nB\right)$
• für TSP: Laufzeit $\mathcal{𝒪}\left(n{2}^n\right)$

Algorithmus heißt Pseudopolynomiell, wenn die Laufzeit durch ein Polynom in $\ell$ und $max$ beschränkt werden kann.

• Dynamisches Programm für Rucksackproblem ist Pseudopolynomiell

Für ein Problem $P$:

• betrachte das Teilproblem $P^{\prime }$
• nur Eingaben polynomiell in $\ell$ erlaubt

Falls $P$ einen pseudopolynomiellen Algorithmus hat:

• dann ist $P^{\prime }$ in $P$

Falls $P^{\prime }$ NP-vollständig ist,

• dann heißt $P$ stark NP-vollständig.

Zum Beispiel TSP.

• Typisch: Zahlen in Binärdarstellung
• alternativ: unäre Darstellung.
  • 1: 1
  • 2: 11
  • 3: 111, ...

Warum gerade Binärdarstellung?

• Algorithmen für NP-vollständige Probleme typischerweise polynomiell auf unärer Eingabe
• Übergang von binär auf ternär, dezimal, ... ändert Zugehörigkeit zu P und NP nicht

Viele Hinweise, dass $P\ne NP$

• Nichtdeterminismus gefühlt viel stärker als Determinismus
• viele (tausende) Probleme gleich schwer (NP-vollständig)
• viele Menschen haben für keins der Probleme effizienten Algorithmus gefunden
• effizienter Algorithmus für ein schweres Problem löst alle
• exponentieller Sprung von Unär- zu Binärdarstellung

Viele Gründe sprechen für $P\ne NP$!

• nicht als Dogma annehmen
• muss wissenschaftlich hinterfragt werden

The P-versus-NP page

• „Beweise“ und „Gegenbeweise“