|
|
\documentclass[11pt]{scrartcl}
|
|
|
\usepackage[utf8]{inputenc}
|
|
|
\usepackage[ngerman]{babel}
|
|
|
\usepackage{amsmath}
|
|
|
\usepackage{amssymb}
|
|
|
\usepackage{marvosym} % Lightning
|
|
|
\usepackage{multicol}
|
|
|
\usepackage{framed}
|
|
|
\usepackage{enumerate}
|
|
|
\usepackage{wrapfig}
|
|
|
%\usepackage{booktabs}
|
|
|
%\usepackage{pstricks}
|
|
|
%\usepackage{pst-node}
|
|
|
\usepackage[paper=a4paper,left=30mm,right=20mm,top=20mm,bottom =25mm]{geometry}
|
|
|
\usepackage[
|
|
|
pdftitle={Berechenbarkeit und Komplexitaetstheorie},
|
|
|
pdfsubject={Mitschrift der Vorlesung "Berechenbarkeit und Komplexitaetstheorie" an der HTW-Aalen, bei Herrn Thierauf.},
|
|
|
pdfauthor={Thomas Battermann},
|
|
|
pdfkeywords={Berechenbarkeit und Komplexitaetstheorie},
|
|
|
pdfborder={0 0 0}
|
|
|
]{hyperref}
|
|
|
\usepackage{tabularx}
|
|
|
\usepackage{graphicx}
|
|
|
\usepackage[usenames,dvipsnames]{color}
|
|
|
\usepackage{lastpage}
|
|
|
\usepackage{fancyhdr}
|
|
|
\setlength{\parindent}{0ex}
|
|
|
\setlength{\parskip}{2ex}
|
|
|
\setcounter{secnumdepth}{4}
|
|
|
\setcounter{tocdepth}{4}
|
|
|
\definecolor{darkgreen}{rgb}{0,0.5,0}
|
|
|
\definecolor{darkblue}{rgb}{0,0,0.5}
|
|
|
\definecolor{greenblue}{rgb}{0,0.5,0.5}
|
|
|
\definecolor{lightgreen}{rgb}{0.25,.75,0.25}
|
|
|
\definecolor{lightblue}{rgb}{0.25,0.25,0.75}
|
|
|
|
|
|
\renewenvironment{leftbar}[1]{%
|
|
|
\def\FrameCommand{{{\vrule width #1\relax\hspace {8pt}}}}%
|
|
|
\MakeFramed {\advance \hsize -\width \FrameRestore }%
|
|
|
}{%
|
|
|
\endMakeFramed%
|
|
|
}
|
|
|
|
|
|
\pagestyle{fancy} %eigener Seitenstil
|
|
|
\fancyhf{} %alle Kopf- und Fußzeilenfelder bereinigen
|
|
|
\fancyhead[L]{Berechenbarkeits.- Komplex.Th.} %Kopfzeile links
|
|
|
\fancyhead[C]{Semester 3} %zentrierte Kopfzeile
|
|
|
\fancyhead[R]{WS 2011/2012} %Kopfzeile rechts
|
|
|
\renewcommand{\headrulewidth}{0.4pt} %obere Trennlinie
|
|
|
\fancyfoot[C]{Seite \thepage\ von \pageref{LastPage}}
|
|
|
\renewcommand{\footrulewidth}{0.4pt} %untere Trennlinie
|
|
|
|
|
|
\newcommand{\spa}{\hspace*{4mm}}
|
|
|
\newcommand{\defin}{\textcolor{darkgreen}{\textbf{Def.: }}}
|
|
|
\newcommand{\satz}{\textcolor{darkblue}{\textbf{Satz: }}}
|
|
|
\newcommand{\bew}[1][]{\textcolor{greenblue}{\textbf{Beweis}}#1:}
|
|
|
\newcommand{\bsp}{\textcolor{lightgreen}{\textbf{Bsp.: }}}
|
|
|
\newcommand{\beh}{\textcolor{lightblue}{\textbf{Beh.:}}}
|
|
|
\newcommand{\lemma}{\textbf{Lemma:}}
|
|
|
\newcommand{\rrfloor}{\right\rfloor}
|
|
|
\newcommand{\llfloor}{\left\lfloor}
|
|
|
|
|
|
\title{Berechenbarkeit und Komplexitätstheorie}
|
|
|
\author{Mitschrift von Thomas Battermann}
|
|
|
\date{3. Semester}
|
|
|
|
|
|
\begin{document}
|
|
|
\pagestyle{empty}
|
|
|
|
|
|
\maketitle\thispagestyle{empty}
|
|
|
\tableofcontents\thispagestyle{empty}
|
|
|
|
|
|
\newpage
|
|
|
\pagestyle{fancy}
|
|
|
\setcounter{page}{1}
|
|
|
|
|
|
\section{Turingmaschinen}
|
|
|
|
|
|
Eingabe und Arbeitsband
|
|
|
\begin{tabular}{c|c|c|c|c|c|c}
|
|
|
\hline
|
|
|
& \color{Orange}{\(x_1\)} & \(x_2\) & \(x_3\) & … & \(x_n\) & \\
|
|
|
\hline
|
|
|
\end{tabular}
|
|
|
{\color{Orange}Lese- Schreibkopf}
|
|
|
|
|
|
Abhängig vom Zustand und vom gelesenen Zeichen auf dem Band kann die Maschine:
|
|
|
\begin{itemize}
|
|
|
\item den Zustand wechseln
|
|
|
\item das gelesene Zeichen überschreiben
|
|
|
\item den Lese-Schreib-Kopf um \( \le 1\) Feld auf dem Band nach links oder rechts bewegen.
|
|
|
\end{itemize}
|
|
|
|
|
|
Formal:\\
|
|
|
Ein \underline{Turingmaschine} (TM) M hat 8 Komponenten,\\
|
|
|
\spa \( M = (Z, \Sigma, \Gamma, \delta, Z_0, Z_a, Z_V,\Box ) \)\\
|
|
|
wobei:
|
|
|
\begin{itemize}
|
|
|
\item \(Z\) – Zustände
|
|
|
\item \(\Sigma\) – Eingabealphabet
|
|
|
\item \(\Gamma\) – Arbeitalphabet
|
|
|
\item \(Z_0\) – Anfangszustand
|
|
|
\item \(Z_a\) – akzeptierender Zustand
|
|
|
\item \(Z_V\) – verwerfender Zustand
|
|
|
\item \(\Box\) – Blank \( \in \Gamma \) – \(\Sigma\)
|
|
|
\end{itemize}
|
|
|
|
|
|
Die Übergangsfunktion S,\\
|
|
|
\spa \( \delta: Z \times \Gamma \to Z \times \Gamma \times \{ L,N,R \} \)\\
|
|
|
D.\,h. typische Anweisung ist\\
|
|
|
\spa \( \delta(z,a) = (Z',b,x) \)\\
|
|
|
Wenn M im Zustand z ist und das Zeichen a liest, dann wechselt M in den Zustand \(Z'\), überschreibt a mit b und bewegt den Lese-Schreibkopf um ein Feld nach links, falls \( X=L\)
|
|
|
\begin{itemize}
|
|
|
\item um ein Feld nach rechts, falls \( X=R\)
|
|
|
\item bleibt stehen, falls \( X=N\)
|
|
|
\end{itemize}
|
|
|
|
|
|
Rechnung von M auf Eingabe \( x = x_1 … x_n \in \Sigma^x \):\\
|
|
|
Initial steht x auf dem Eingabeband und der Lese-Schreibkopf auf dem 1. Zeichen \(x_1\) .\\
|
|
|
Links und rechts der Eingabe steht \(\Box\) auf allen Feldern (Beidseitig unbeschränktes Band).\\
|
|
|
Anfangszustand ist \(Z_0\)
|
|
|
Dann fährt die Maschine Schritte gemäß \(\delta\). Die Rechnung stoppt, wenn \(Z_a\) oder \( Z_V\) erreicht wird. x wird akzeptiert, falls \(Z_a\) erreicht wird, sonst wird x verworfen.
|
|
|
|
|
|
Die von \underline{M akzeptierte Sprache} ist\\
|
|
|
\spa \( L(M) = \{ x \in \Sigma* \mid M \text{ akzeptiert } x \} \)
|
|
|
Bsp. Sei \( \Sigma = \{ 0,1 \} \)\\
|
|
|
\spa Berechne \(f(x) = x+1 \)\\
|
|
|
\begin{tabular}{c|c|c|c|c}
|
|
|
\hline
|
|
|
\(\Box\) & 1& 0 & 1 & \(\Box\) \\
|
|
|
\hline
|
|
|
\end{tabular} \( \to \)
|
|
|
\begin{tabular}{c|c|c|c|c}
|
|
|
\hline
|
|
|
\(\Box\) & 1& 1 & 0 & \(\Box\) \\
|
|
|
\hline
|
|
|
\end{tabular}
|
|
|
|
|
|
Der berechnete Funktionswert ist definiert als das Wort \( \in \Sigma* \) von der Position des Lese-Schreibkopfs nach rechts, bis zu 1. Blank.\\
|
|
|
In \(Z_a\).
|
|
|
|
|
|
\( \sigma(Z_0,0) = (Z_0, 0, R) \)\\
|
|
|
\( \sigma(Z_0,1) = (Z_0, 1, R) \)\\
|
|
|
\( \sigma(Z_0,\Box) = (Z_1, \Box, L) \)\\
|
|
|
\( \sigma(Z_1,0) = (Z_2, 1, L) \)\\
|
|
|
\( \sigma(Z_1,1) = (Z_1, 0, L) \)\\
|
|
|
\( \sigma(Z_2,0) = (Z_2, 0, L) \)\\
|
|
|
\( \sigma(Z_2,1) = (Z_2, 1, L) \)\\
|
|
|
\( \sigma(Z_2,\Box) = (Z_a, \Box, R) \)\\
|
|
|
\( \sigma(Z_1,\Box) = (Z_a, 1, N) \)
|
|
|
|
|
|
Als Diagramm
|
|
|
% TODO
|
|
|
|
|
|
\( L = \{ 0^{2^n} \mid n \ge 0 \} \)\\
|
|
|
\( 0, 00, 0^4, 0^8, …\)
|
|
|
|
|
|
\begin{tabular}{c|c|c|c|c|c}
|
|
|
\hline
|
|
|
& 0 & 0 & 0 & 0 & \\
|
|
|
\hline
|
|
|
\end{tabular}
|
|
|
|
|
|
\begin{enumerate}
|
|
|
\item Vorschlag: Zähle\\
|
|
|
\begin{tabular}{c|c|c|c|c|c}
|
|
|
\hline
|
|
|
& \( \not0\) & 0 & … 0 & \( \Box \) & 0\\
|
|
|
\hline
|
|
|
\end{tabular}
|
|
|
\item Vorschlag:\\
|
|
|
\begin{enumerate}
|
|
|
\item streiche jede 2. Null, teste dabei, ob Anzahl gerade
|
|
|
\item iteriere Schritt 1\\
|
|
|
bis nur noch eine Null bleibt.\\
|
|
|
% TODO: Diagramm
|
|
|
\( 0000 \to 0x0x \to 0xxx \)
|
|
|
\end{enumerate}
|
|
|
\end{enumerate}
|
|
|
|
|
|
\subsection{Erweiterungen}
|
|
|
|
|
|
\subsubsection{Mehrband-Turingmaschine}
|
|
|
|
|
|
Turingmaschine mit fester Anzahl k von Bändern. Davon eins ausgezeichnet für die Eingabe.\\
|
|
|
\( \delta: Z \times \Gamma^k \to Z \times \Gamma^k \times \{ L,N,R \}^k \)
|
|
|
|
|
|
Bsp.:\\
|
|
|
\( \delta(Z,a,b) = \delta(Z', c,d,L,R) \)
|
|
|
|
|
|
Bsp.: \( L = \left\{ w \# w \mid w \in \{0,1\}^k \right\} \)\\
|
|
|
\( 100\#100 \to x00\#x00 …\)
|
|
|
|
|
|
\underline{2-Band-Turingmaschine}\\
|
|
|
kopiert w auf 2. Band\\
|
|
|
\spa \( \delta(Z_0, a, \Box) = (Z_0,a,a,R,R) \) für \( a \in \{1,0\}\)\\
|
|
|
\spa \( \delta(Z_0, \#,\Box) = (Z_1, \#,\Box, N,L) \)\\
|
|
|
\spa \( \delta(Z_1, \#,\Box) = (Z_1, \#,a, N,L)\)\\
|
|
|
\spa \( \delta(Z_1, \#,\Box) = (Z_2, \#,\Box,R,R) \)\\
|
|
|
\spa \( \delta(Z_2, a,a) = (Z_2,a,a,R,R) \)\\
|
|
|
\spa \( \delta(Z_2, \Box,\Box) = (Z_a, \Box,\Box,N,N) \)
|
|
|
|
|
|
Alles was fehlt geht nach \( Z_V \)
|
|
|
|
|
|
\subsubsection{Nichtdeterministische Turingmaschine (NTM)}
|
|
|
|
|
|
Definiert wie Turingmaschine, mit:\\
|
|
|
\spa \( \delta: Z\times \Gamma \to \mathcal{P}(Z \times \Gamma \times \{ L,N,R \}) \)\\
|
|
|
z.\,B. \( \delta(Z,a) = \{ (Z_1,b,L) , (Z_2,c,N) \} \)
|
|
|
|
|
|
M akzeptiert x, falls es eine akzeptierende Rechnung gibt.
|
|
|
|
|
|
\subsubsection{Nichtdeterministische Mehrband Turingmaschine}
|
|
|
|
|
|
Bsp. \( L = \{ x0y \mid \left|x\right| = \left|y\right| \}\)\\
|
|
|
über \( \Sigma = \{0,1\}\)
|
|
|
|
|
|
\begin{align*}
|
|
|
\delta(Z_0, 1, \Box) &= \{( Z_0,1,1,R,R )\}\\
|
|
|
\delta(Z_0,0,\Box) &= \{ (Z_0,0,0,R,R), (Z_1,0,\Box,R,L) \} \\
|
|
|
\delta(Z_1,a,b) &= \{ (Z_1,a,b,R,L) \} \quad a,b \rightarrow \{0,1\}\\
|
|
|
\delta(Z_1,\Box,\Box) &= \{ (Z_a,\Box,\Box,N,N) \}\\
|
|
|
\delta(Z_0,\Box,\Box) &= \{ (Z_v,\Box,\Box,N,N) \}\\
|
|
|
\end{align*}
|
|
|
(fehlende Anweisungen verwerfen.)
|
|
|
|
|
|
Deterministisch: \(\delta: Z\times \Gamma \to Z \times \Gamma \times \{ L,N,R\} \)\\
|
|
|
Nicht Deterministisch: \(\delta: Z\times \Gamma \to \mathcal P(Z \times \Gamma \times \{ L,N,R\}) \)
|
|
|
|
|
|
\satz Zu jeder k-Band Turingmaschine gibt es eine äquivalente (1-Band) Turingmaschine\\
|
|
|
\underline{Bew.:} (Idee)\\
|
|
|
k-Band Turingmaschine M\\\
|
|
|
\begin{tabular}{c|c|c|c|c} \hline & x & & & \\\hline & & y & & \\\hline & & & z & \\\hline \end{tabular}
|
|
|
|
|
|
TM M'\\
|
|
|
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
|
|
|
\hline & \# & x & & & \# & & y & & \# & & & z & \# & \\\hline
|
|
|
\end{tabular}
|
|
|
|
|
|
M:\\
|
|
|
\begin{tabular}{c|c|c|c|c|c}
|
|
|
\hline
|
|
|
\(\Box\)&a&b&a&c&\(\Box\)\\
|
|
|
\hline
|
|
|
\(\Box\)&c&c&\(\Box\)\\
|
|
|
\hline
|
|
|
\(\Box\)&b&a&a&a&\(\Box\)\\
|
|
|
\hline
|
|
|
\end{tabular}
|
|
|
|
|
|
M':\\
|
|
|
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
|
|
|
\hline
|
|
|
\# & \(\Box\)& a& \(\dot b\)& a&c&\(\Box\)&\#&\(\Box\)&\(\dot c\)&a&\(\Box\) & \# & \(\dot\Box\) & b&a&a&a&\(\Box\)&\#\\
|
|
|
\hline
|
|
|
\end{tabular}\\
|
|
|
\( \dot b \rightarrow \Gamma' - \Gamma \)
|
|
|
|
|
|
M' läuft 2x mal über das gesamte Band (und zurück)
|
|
|
\begin{enumerate}
|
|
|
\item M' merkt sich alle Zeichen, die die Lese-Schreibköpfe aktuell lesen
|
|
|
\item M' führt die Änderungen gemäß \(\delta\) von M auf allen Bändern aus.
|
|
|
\end{enumerate}
|
|
|
|
|
|
Merke Zeichen im Zustand:\\
|
|
|
\spa \( Z_{Z,b,c,\Box} \)\\
|
|
|
d.\,h. \(\left|Z\right| \cdot \left|\Gamma\right|^3 \) viele Zustände, also endlich.
|
|
|
|
|
|
Initial:\\
|
|
|
\begin{tabular}{c|c|c|c|c|c|c}
|
|
|
\hline
|
|
|
\# & x & \# & \(\Box\) & \# & \(\Box\) &\#\\
|
|
|
\hline
|
|
|
\end{tabular}
|
|
|
|
|
|
Zeit: M macht t Schritte auf Eingabe X.\\
|
|
|
Alle Bänder von M' sind also mit Wörtern beschriftet mit Länge \(\le t\)\\
|
|
|
\(\to\) Beschrifteter Teil des Bands von M hat Länge \(\le k \cdot t \)
|
|
|
|
|
|
Pro Schritt von M macht M'
|
|
|
\begin{itemize}
|
|
|
\item \( \le 2 \cdot 2 \cdot t \) Schritte für die beiden Durchläufe.
|
|
|
\item verschieben zum Platz schaffen \( \le k \cdot 2\cdot t\)
|
|
|
\item Zusammen \( \le (k+2) \cdot 2\cdot t = \mathcal O(t)\).\\
|
|
|
M macht t Schritte \( \Rightarrow M' \) macht \( \mathcal O(t^2) \) Schritte
|
|
|
\end{itemize}
|
|
|
|
|
|
\satz Zu jeder NTM gibt es eine äquivalente TM.
|
|
|
|
|
|
Bew. (Idee):\\
|
|
|
Sei M NTM
|
|
|
|
|
|
Strategie: durchsuche Baum "Breite zuerst". Dazu zunächst Mehrband-TM (det.).\\
|
|
|
|
|
|
Pro Adresse:
|
|
|
\begin{itemize}
|
|
|
\item Kopiere x auf das (leere) Simulationsband,
|
|
|
\item führe Rechnung von M auf x aus, wobei jeweils die Anweisung gemäß Adresse benützt wird.
|
|
|
\item falls M akzeptiert wird, dann akzeptierte.
|
|
|
\end{itemize}
|
|
|
|
|
|
Bann lösche Simulationsband, erhöhe Adresse um 1 (zur Basis d) und wiederhole.
|
|
|
|
|
|
Zeit: Habe jede Rechnung von M die länge \(\le t\)\\
|
|
|
\(\Rightarrow\) Anzahl der Knoten im Baum ist \( \le d^{t+1} - 1 \)\\
|
|
|
\(\Rightarrow\) Rechenzeit von M': \(\mathcal O(t+n)\cdot d^t\)\\
|
|
|
\(\Rightarrow\) Rechenzeit der det. 1-Band TM M'' ist dann \( \mathcal O\left(\left(\left(t+n\right) \cdot d^t\right)^2\right) \)
|
|
|
|
|
|
\begin{align*}
|
|
|
&\mathcal O(t^2 2^{2t \cdot \log d})\\
|
|
|
= &\mathcal O(2^{2 \log t} \cdot 2^{2 \cdot \log d})\\
|
|
|
= &\mathcal O(2^{2t \log d + 2 \log t})\\
|
|
|
= &\mathcal O(2^{2^{2t(\log d + 1)}})\\
|
|
|
= & 2^{\mathcal O(t)}
|
|
|
\end{align*}
|
|
|
|
|
|
Weitere Rechenmodelle haben sich alle als äquivalent zur TM erwiesen. Insbesondere lässt sich jedes C-Programm in eine äquivalente TM umschreiben.
|
|
|
|
|
|
\underline{These von Turing/Church}
|
|
|
|
|
|
Algorithmus = TM
|
|
|
intuitiver Begriff = formal
|
|
|
|
|
|
\subsection{Kodierung von Turingmaschinen}
|
|
|
|
|
|
Sei M TM mit \( Z = \{ Z_1, Z_2, …, Z_k \}\) und \( \Sigma \le \Gamma = \{ a_1, a_2, …, a_m \} \)\\
|
|
|
Sei \( \delta(Z_i,a_j) = (Z_{i'}, a_{j'}, d) \)\\
|
|
|
\( d = \{ L,M,R \} \)
|
|
|
|
|
|
Kodiere mit:\\
|
|
|
\( x_{i,j} = 0 1^i 0 1^j 0 1^{i'} 0 1^{j'} 0 1^{d'} 0 \)
|
|
|
|
|
|
mit \( d = \begin{cases} 1 & \text{,falls d = L} \\ 2 & \text{,falls d = N} \\ 3 & \text{,falls d = R} \end{cases} \)
|
|
|
|
|
|
Kodiere M durch\\
|
|
|
\( x = x_{1,1} x_{1,2} … x_{1,m} x_{2,1} … x_{k,m} \)
|
|
|
|
|
|
Dabei lege fest: \(Z_1\) ist Startzustand; \( Z_{k-1} \) ist \(Z_V\); \(Z_k\) ist \( Z_a \)\\
|
|
|
und \( a_1 = \Box \)
|
|
|
|
|
|
Damit besitzt jede Turingmaschine M eine Kodierung \( x \in \{0,1\}^* \). x heißt auch \underline{Index} oder \underline{Gödelnummer von M}\\
|
|
|
Nicht jedes Wort aus \(\{0,1\}^*\) taucht als Kodierung gemäß obigem Schema auf.\\
|
|
|
Deswegen: Für \(x\in \{0,1\}^* \)\\
|
|
|
\( x \to \begin{cases} M_x & \text{, falls Kodierung von } M_x x \text{ ergibt}\\ M_0 & \text{, sonst} \end{cases} \)\\
|
|
|
\(M_0\) fest, mit \( L(M_0) = \emptyset \)
|
|
|
|
|
|
Mit dieser Festlegung kodiert \underline{jedes} Wort \( x \in \{0,1\}^* \) eine TM \(M_x\).
|
|
|
|
|
|
D.\,h. \( \{0,1\}^* = \{ \epsilon, 0, 1, 00, 01, 10, 11, 000, … \} \)\\
|
|
|
dies ist eine Aufzählung aller 0-1-Wörter und damit auch aller Turingmaschinen.
|
|
|
|
|
|
\subsection{Das Halteproblem}
|
|
|
|
|
|
\( H = \{ (x,y) \mid M_y(x) \text{ hält} \} \)\\
|
|
|
dabei sei \((x,y) = x_1 x_1 x_2 x_2 … x_n x_n 01 y \)\\
|
|
|
\( (010, 10) = \begin{cases} 000101010 \\ 00 11 00 10 \underbrace{10}_{y} \end{cases} \)
|
|
|
|
|
|
\subsection{Die Universalsprache}
|
|
|
|
|
|
\( U = \{ (x,y) \mid M_y \text{ akzeptiert } x \} \)
|
|
|
|
|
|
Eine Sprache L heißt (Turing-) \underline{akzeptierbar}, falls es eine Turingmaschine M gibt, mit \( L(M) = L \).
|
|
|
|
|
|
L heißt (Turing-) \underline{entscheidbar}, falls M zusätzlich auf alle Eingaben hält.
|
|
|
|
|
|
U ist akzeptierbar:\\
|
|
|
Beschreibe zunächst eine 3-Band-Turingmaschine\\
|
|
|
M für U\\
|
|
|
M: \begin{tabular}{c|c|c}
|
|
|
\hline
|
|
|
&\((x,y)\)&\\
|
|
|
\hline
|
|
|
\end{tabular}\\
|
|
|
\(\underset{Z_1\text{ Startzustand}}{\to}\)\\
|
|
|
\begin{tabular}{c|c|c|c|c|c}
|
|
|
\hline
|
|
|
&\(x_1\)&\(x_2\)&…&\(x_n\)&\\
|
|
|
\hline
|
|
|
& \(Z_1 \) &\\
|
|
|
\hline
|
|
|
&\(y\)&\\
|
|
|
\hline
|
|
|
\end{tabular}\\
|
|
|
dann simuliere \(M_y\) auf dem 1. Band
|
|
|
|
|
|
d.\,h. Suche in y die Stelle wo \( \delta(Z_1,x_1)\) definiert ist und führe dann Änderungen auf dem 1. Band aus. * Dann gehe auf Band 2 und 3 wieder nach links und wiederhole.\
|
|
|
Abbruch wenn \(M_y\) \(Z_a\) oder \(Z_v\) erreicht.
|
|
|
|
|
|
* Auf Band 2 ändere den Zustand.
|
|
|
|
|
|
M akzeptiert, falls \(M_y\) \(Z_a\) erreicht und verwirft bei \(Z_v\).
|
|
|
|
|
|
Dann gilt:\\
|
|
|
\begin{itemize}
|
|
|
\item \((x,y) \in U \Rightarrow M_y(x) \) akzeptiert.\\
|
|
|
\(\Rightarrow M_y(x)\) kommt nach endlich vielen Schritten nach \(Z_a\)\\
|
|
|
\(\Rightarrow M(x,y)\) akzeptiert
|
|
|
\item \( (x,y) \not\in U \Rightarrow M_y(x)\) verwirft.
|
|
|
\begin{enumerate}[a)]
|
|
|
\item] \( M_y(x) \) erreicht \(Z_v\)\\
|
|
|
\( \Rightarrow M(x,y)\) verwirft.
|
|
|
\item \( M_y(x) \) hält nicht\\
|
|
|
\( \Rightarrow M(x,y) \) hält nicht.\\
|
|
|
\( \Rightarrow M(x,y) \) verwirft.
|
|
|
\end{enumerate}
|
|
|
\end{itemize}
|
|
|
|
|
|
Es gibt also \( L(M) = U \).\\
|
|
|
Sei \(M_U\) die zu M äquivalente (1-Band) Turingmaschine.\\
|
|
|
\(M_U\) heißt \underline{universelle Turingmaschine}.
|
|
|
|
|
|
Analog ist H akzeptierbar.\\
|
|
|
(nehme M von oben und akzeptiere auch, wenn \(Z_v\) erreicht wird.)
|
|
|
|
|
|
Bezeichnungen:\\
|
|
|
\begin{itemize}
|
|
|
\item akzeptierbar
|
|
|
\subitem rekursiv aufzählbar
|
|
|
\subitem semi-entscheidbar
|
|
|
\subitem partiell rekursiv
|
|
|
\item entscheidbar
|
|
|
\subitem rekursiv
|
|
|
\end{itemize}
|
|
|
|
|
|
Wir Konstruieren eine Sprache $D$, die nicht \underline{nicht} akzeptierbar ist.\\
|
|
|
D.\,h. \( D \not= L(M) \) für alle Turingmaschinen M.
|
|
|
|
|
|
\begin{tabular}{c|ccccc}
|
|
|
TM \( \backslash \Sigma^*\) & \(x_1\) &\(x_2\) &\(x_3\) &\(x_4\) & … \\
|
|
|
\hline
|
|
|
\(x_1\) & 0 & 1 & 0 & 0 & …\\
|
|
|
\(x_2\) & 1 & 0 & 1 & 1 & \\
|
|
|
\(x_3\) & 0 & 0 & 1 & 1 & \\
|
|
|
\(x_4\) & 1 & 0 & 1 & 0 & …\\
|
|
|
\(\vdots\) & & & & \(\vdots\)
|
|
|
\end{tabular}\\
|
|
|
\( M_{x_1} (x_3)\) verwirft\\
|
|
|
\( M_{x_1} (x_4)\) akzeptiert
|
|
|
|
|
|
Jede Zeile in der Tabelle beschreibt eine Sprache:\\
|
|
|
Zeile $i$: die von \( M_{x_i}\) akzeptierte Sprache.\\
|
|
|
Wir konstruieren $D$ so, dass $D$ mit \underline{keiner} Zeile der Tabelle übereinstimmt.
|
|
|
|
|
|
\( D = \{ x \mid x \not\in L(M_x)\} \)
|
|
|
|
|
|
Dann ist $D$ nicht akzeptierbar:
|
|
|
|
|
|
Angenommen \( D = L(M) = L(M_x) \)\\
|
|
|
für ein \( x \in \Sigma^* \)
|
|
|
|
|
|
Es gilt aber \( x\in D \leftrightarrow x \not\in L(M_x) \)\\
|
|
|
Widerspruch!
|
|
|
|
|
|
\subsection{Diagonalsprache}
|
|
|
|
|
|
\( D = \{ x \mid x \not\in L(M_X) \} \) ist nicht \underline{akzeptierbar}.
|
|
|
|
|
|
%%TODO: Grafik
|
|
|
|
|
|
\( U = \{ (x,y) \mid i\underbrace{M_y \text{ akzeptiert } x}_{x \in L(M_y)} \} \)
|
|
|
|
|
|
\satz $H$ und $U$ sind nicht entscheidbar.
|
|
|
|
|
|
Beweis zu $U$: Angenommen $U$ wäre entscheidbar. D.\,h. es gibt eine Turingmaschine $M$, die $U$ akzeptiert die auf alle Eingaben hält.\\
|
|
|
Dann entscheidet folgende Turingmaschine $M'$ die Sprache $D$:
|
|
|
|
|
|
\( D = \{ x \mid (x,x) \not\in U \} \)\\
|
|
|
\( H = \{ (x,y) \mid M_y \text{ auf } x \text{ hält } \} \)
|
|
|
|
|
|
$M'$:
|
|
|
\begin{leftbar}{1mm}
|
|
|
Eingabe $x$.\\
|
|
|
Starte $M$ auf Eingabe $(x,x)$\\
|
|
|
Falls $M$ akzeptiert, dann verwerfe, sonst akzeptiere.
|
|
|
\end{leftbar}
|
|
|
|
|
|
Da $M$ immer hält, hält auch $M'$ auf alle Eingaben und $L( M') = D$.\\
|
|
|
Widerspruch, da $D$ nicht entscheidbar. $\Box$
|
|
|
|
|
|
\underline{Zu $H$:} Angenommen $H$ ist entscheidbar, $H=L(M)$.\\
|
|
|
Konstruiere $M'$ für $D$:\\
|
|
|
$M'$:
|
|
|
\begin{leftbar}{1mm}
|
|
|
Eingabe $x$\\
|
|
|
Starte $M$ auf Eingabe $(x,x)$.\\
|
|
|
Falls $M$ akzeptiert
|
|
|
\begin{leftbar}{1mm}
|
|
|
dann starte $M_x$ auf $x$\\
|
|
|
falls $M_x$ akzeptiert, dann verwerfe\\
|
|
|
sonst akzeptiere
|
|
|
\end{leftbar}
|
|
|
sonst akzeptiere
|
|
|
\end{leftbar}
|
|
|
|
|
|
\begin{enumerate}
|
|
|
\item \( (x,x) \in H \to M_x(x) \) hält\\
|
|
|
und \( x \in D \leftrightarrow M_x \) verwirft
|
|
|
\item \( (x,x) \not\in H \Rightarrow M_x(x)\) hält nicht\\
|
|
|
\( \Rightarrow M_x \) verwirft $x$\\
|
|
|
\( \Rightarrow x \in D \)\\
|
|
|
Es gilt.: $M'$ hält auf alle Eingaben und \( L(M') = D \). Widerspruch \( \Box\)
|
|
|
\end{enumerate}
|
|
|
|
|
|
\subsection{Das spezielle Halteproblem}
|
|
|
|
|
|
\spa \( H_0 = \{ x \mid M_x(x) \text{ hält } \} \)\\
|
|
|
$H_0$ ist akzeptierbar und entscheidbar.
|
|
|
|
|
|
\underline{Zu $H_0$}: Angenommen $H_0$ ist entscheidbar, \( H_0 = L(M)\).
|
|
|
|
|
|
\( T = \{ x \mid M_x \text{ hält auf alle Eingabe }\} \)
|
|
|
|
|
|
Turingmaschine $M$ heißt \underline{total}, falls $M$ auf alle Eingaben hält.
|
|
|
|
|
|
\( L_E = \{ x \mid M_x \text{ hat Eigenschaft } E \} \)
|
|
|
|
|
|
\satz $T$ ist nicht entscheidbar.
|
|
|
|
|
|
\bew Sonst wäre $H$ entscheidbar.\\
|
|
|
Sei $M_T$ Turingmaschine für $T$ (die immer hält)\\
|
|
|
Turingmaschine $M$ für $H$: Eingabe $(x,y)$.\\
|
|
|
Betrachte folgende Turingmaschine $M_0$:
|
|
|
|
|
|
\begin{leftbar}{1mm}
|
|
|
$M_0$ auf Eingabe $w \in \Sigma^*$:\\
|
|
|
\spa Simuliere $M_y(x)$\\
|
|
|
\spa Falls $M_y(x)$ hält, dann akzeptiere
|
|
|
\end{leftbar}
|
|
|
|
|
|
\begin{itemize}
|
|
|
\item[1. Fall:]
|
|
|
\( (x,y) \in H \Rightarrow M_y(x) \) hält.\\
|
|
|
\( \Rightarrow M_0 \) akzeptiert\\
|
|
|
\( L(M_0) = \Sigma^* \)
|
|
|
\item[2. Fall:]
|
|
|
\( (x,y) \not\in H \Rightarrow M_0\) hält nicht\\
|
|
|
\( \Rightarrow M_0 \) verwirft\\
|
|
|
\( \Rightarrow L(M_0) = \emptyset \)
|
|
|
\end{itemize}
|
|
|
|
|
|
Sei $y_0$ Kodierung von $M_0$.\\
|
|
|
Dann gilt:\\
|
|
|
\spa \( (x,y) \in H \Leftrightarrow y_0 \in T \)
|
|
|
|
|
|
$M$ für $H$:\\
|
|
|
\begin{leftbar}{1mm}
|
|
|
Eingabe $(x,y)$\\
|
|
|
Konstruiere Turingmaschine $M_0$ (aus $x$ wird $y$)\\
|
|
|
Sei $y_0$ Kodierung von $M_0$\\
|
|
|
Falls $y_0 \in T$, dann akzeptiere\\
|
|
|
Sonst verwerfe
|
|
|
\end{leftbar}
|
|
|
|
|
|
\begin{itemize}
|
|
|
\item[1. Fall]
|
|
|
\( (x,y) \in H \Rightarrow M_x(x) \) hält\\
|
|
|
\( \Rightarrow L(M_0) = \Sigma^* \) \\
|
|
|
\( \Rightarrow \) insbesondere hält $M_0$ auf alle Eingaben\\
|
|
|
\( \Rightarrow y_0 \in T \)\\
|
|
|
\( \Rightarrow M \) akzeptiert \( (x,y) \)
|
|
|
\item[2. Fall]
|
|
|
\( (x,y) \not\in H \Rightarrow L(M_0) = \emptyset \) und $M_0$ hält auf \underline{\underline{keine}} Eingabe\\
|
|
|
d.\,h. $M$ entscheidet $H$ Widerspruch \( \Box \)
|
|
|
\end{itemize}
|
|
|
|
|
|
\( L_E = \{ x \mid \text{Turingmaschine } M_x \text{ hat }\underbrace{\text{Eigenschaft}}_{\text{Spracheigenschaft}} E \} \)
|
|
|
|
|
|
ist unentscheidbar für jede Eigenschaft $E$.
|
|
|
|
|
|
\subsubsection{Satz von Rice}
|
|
|
|
|
|
\bsp \( F = \{ x \mid L(M_x) \text{ ist endlich} \} \)
|
|
|
|
|
|
finite: \( \overline{F} = \{ x \mid L(M_x) \text{ ist unendlich} \} \)
|
|
|
|
|
|
empty: \( E = \{ x \mid L(M_x) = \emptyset \} \)
|
|
|
|
|
|
\( S = \{ x \mid L(M_x) = \Sigma^* \)
|
|
|
|
|
|
Äquivalenz \( = \{ (x,y) \mid L(M_x) = L(M_y) \} \)
|
|
|
|
|
|
Äquivalenz für alle Sprachen\\
|
|
|
\spa \( = \{ (x,y) \mid x,y \text{ sind PDAs und } L(M_y) = L(M_y) \} \)\\
|
|
|
ist unentscheidbar.
|
|
|
|
|
|
\underline{Gödel}: mehrere Arithmetische Formeln:\\
|
|
|
\( \forall n \exists m : (n=2m \text{ oder } n=2m-1) \) wahr\\
|
|
|
\( \forall n \exists m: n=2m \) falsch
|
|
|
|
|
|
\subsubsection{Post’sches Korrespondenz Problem (PCP)}
|
|
|
|
|
|
gegeben sind Dominos der Form \( \left[ \frac x y \right] \)\\
|
|
|
wobei \(x,y \in \Sigma^* \), endlich viele Typen, von jedem Type beliebig viele.
|
|
|
|
|
|
\bsp \( D = \{ \left[ \frac{b}{ca} \right], \left[ \frac{a}{ab} \right], \left[ \frac{ca}{a} \right], \left[ \frac{abc}{c} \right] \} \)
|
|
|
|
|
|
Ziel: lege Dominos so, dass das Wort, das oben steht gleich dem ist, das unten steht.
|
|
|
|
|
|
\( \left[ \frac{a}{ab} \right] \left[ \frac{b}{ca} \right] \left[ \frac{ca}{a} \right] \left[ \frac{abc}{c} \right] \) Widerspruch!\\
|
|
|
\( \left[ \frac{a}{ab} \right] \left[ \frac{b}{ca} \right] \left[ \frac{ca}{a} \right] \left[ \frac{a}{ab} \right] \left[ \frac{abc}{c} \right] \)
|
|
|
|
|
|
$D$ hat Lösung, also \( D \in PCP \)
|
|
|
|
|
|
\( D_1 = \{ \left[ \frac{ab}{abc} \right] \left[ \frac{c}{ab} \right] \left[ \frac{ac}{cab} \right] \left[ \frac{ba}{acb} \right] \)
|
|
|
|
|
|
\( \left[ \frac{ab}{abc} \right]\left[ \frac{c}{ab} \right] \)
|
|
|
|
|
|
hat keine Lösung, da Wörter unten immer Länger als Wörter oben sind. \( D_1 \not\in PCP \)
|
|
|
|
|
|
\bsp \( \{ \left[ \frac{0}{011} \right] \left[ \frac{001}{1} \right] \left[ \frac{1}{00} \right] \left[ \frac{11}{110} \right] \} \)\\
|
|
|
Kürzeste Lösung hat 515 Dominos.
|
|
|
|
|
|
PCP ist unentscheidbar
|
|
|
|
|
|
\section{Eulerkreise}
|
|
|
|
|
|
Rundweg in $G$, der über \underline{jede} Kante \underline{genau einmal} führt.\\
|
|
|
Kreis \( = (1,5,2,3,1,2,4,6,3,4) \)
|
|
|
|
|
|
Ein Eulescher Kreis besucht jeden Knoten gerade oft, d.\,h. jeder Knoten muss geraden Grad haben.\\
|
|
|
\satz (Euler) $G$ ungerichtet, zusammenhängend\\
|
|
|
$G$ hat Eulerkreis \( \Leftrightarrow \) jeder Knoten hat geraden Grad.
|
|
|
|
|
|
Zu "\(\Leftarrow\)":
|
|
|
Konstruiere Eulerkreis\\
|
|
|
Starte an beliebigem Knote, der noch unbesuchte Knoten hat. Laufe in beliebige Richtung, solange bis es nicht mehr weiter geht.\\
|
|
|
Falls es noch unbesuchte Kanten gibt, wiederhole.\\
|
|
|
Füge (rekursiv) die Kreise zu einem Kreis zusammen.
|
|
|
|
|
|
Der Algorithmus funktioniert, weil in jeder Iteration in dem Restgraph mit dem noch unbesuchten Kanten jeder Knoten geraden Grad hat. (Invariante)
|
|
|
|
|
|
\section{Hamilton Kreise}
|
|
|
|
|
|
= Kreise, in denen jeder Knoten genau einmal besucht wird.
|
|
|
|
|
|
Brute force: teste alle Möglichkeiten.\\
|
|
|
n Knoten. Liste alle Permutationen der n Knoten auf.\\
|
|
|
\(1,2, 3, …, n\)\\
|
|
|
\(2,1,3,…,n\)\\
|
|
|
…
|
|
|
|
|
|
für jede Permutation teste, ob sie ein Hamilton Kreis ist d.\,h. ob alle Kreiskanten in $G$ existieren.\\
|
|
|
Laufzeit \( \ge n! \) (im schlechtesten Fall)\\
|
|
|
\( n! \approx 2^{n \log n} \ge 2^n \)\\
|
|
|
also exponentielle Laufzeit.
|
|
|
|
|
|
(Sehr schneller) Rechner mit \( 10^9 \frac{\text{instructions}}{s} \)\\
|
|
|
\( n = 100 \)\\
|
|
|
\begin{tabular}{c|c|c|c|c}
|
|
|
$t(n)$ & $n$ & $n^2$ & $n^3$ & $2^n$ \\
|
|
|
\hline
|
|
|
Zeit & $\frac{1}{10^7}$ & $\frac{1}{10^4}$ & $\frac{1}{10^2}$ & \( \frac{2^{100}}{10^9} = \frac{(2^{10})^{10}}{10^9} \approx \frac{(10^3)^{10}}{10^9} = 10^{21} s = 3 * 10^{13} \) Jahre
|
|
|
\end{tabular}
|
|
|
|
|
|
Schnellere Hardware:\\
|
|
|
Sei $n_0$ = Eingabegröße, die in 1h gelöst wird.\\
|
|
|
Neue Rechner, 1000-mal schneller als bisher.\\
|
|
|
Berechne $n_1$ = Eingabegröße, die in einer Stunde mit den neuen Rechnern gelöst wird.
|
|
|
\begin{enumerate}
|
|
|
\item
|
|
|
\( t(n) = n \)\\
|
|
|
1h. \( t(n_1) = 1000 t(n_0) \)\\
|
|
|
\( n_1 = 1000 * n_0 \)
|
|
|
\item
|
|
|
\( t(n) = n^2: n_1^2 = 1000*n_0^2 \)\\
|
|
|
\( n1 = \underbrace{\sqrt{1000}}_{\approx 33} * n_0 \)
|
|
|
\item
|
|
|
\( t(n) = n^3 \)\\
|
|
|
\( n_1^3 = 1000*n_0^3 \)\\
|
|
|
\( n_1 = 10 * n_0 \)
|
|
|
\item
|
|
|
\( t(n) = 2^n \)\\
|
|
|
\( 2^{n_1} = 1000 * 2^{n_0} = 2^{n_0 + \log 1000} \)\\
|
|
|
\( \Rightarrow n_1 = n_0 + \underbrace{\log 1000}_{\le 10} \)
|
|
|
\end{enumerate}
|
|
|
|
|
|
Nichtdeterministischer Algorithmus\\
|
|
|
für hamilton Kreis:
|
|
|
|
|
|
Eingabe $G$ mit n Knoten\\
|
|
|
\begin{itemize}
|
|
|
\item Permutation \( \rho \)
|
|
|
\item Prüfe, ob \( \rho \) einen hamilton Kreis beschreibt\\
|
|
|
falls ja, akzeptiere, sonst verwerfe
|
|
|
\end{itemize}
|
|
|
|
|
|
|
|
|
HAM nichtdeterministisch effizient lösbar.
|
|
|
|
|
|
\section{Erfüllbarkeit logischer Formeln, SAT}
|
|
|
|
|
|
\( F(x_1, …, x_n) = (\overline{x_1 \land x_2} \lor x_3) \to (x_4 \land \overline{x_5}) \)\\
|
|
|
Frage: gibt es eine Belegung \( a \in \{0,1\}^n\) so dass \( F(a) = 1 \).
|
|
|
|
|
|
Deterministischer Algorithmus: durchlaufe alle \( a\in \{0,1\}^n\) und teste jeweils, \(F(a)=1\).\\
|
|
|
Laufzeit \( \ge 2^n \), exponentiell.
|
|
|
|
|
|
Nichtdeterministisch: Rate nichtdeterministisch ein \(a\in \{0,1\}^n \) und teste ob \(F(a)=1\).
|
|
|
|
|
|
\begin{tabular}{ccc}
|
|
|
\hline
|
|
|
&F&\\
|
|
|
\hline
|
|
|
\end{tabular}
|
|
|
|
|
|
\begin{tabular}{c|c|c|c|c}
|
|
|
\hline
|
|
|
&x&x&…&x\\
|
|
|
\hline
|
|
|
\end{tabular}
|
|
|
|
|
|
markiere n Bandfelder.\\
|
|
|
fülle diese nichtdeterministisch mir 0 oder 1 aus
|
|
|
|
|
|
\( \delta(Z_1,x) = \{(Z_1,0,N,R),(Z_1,1,N,R)\} \)
|
|
|
|
|
|
KNF-SAT = Erfüllbarkeit für Formeln F in KNF\\
|
|
|
Bsp. \( F = (x_1 \lor \overline{x_2} \lor x_3) \land (x_2 \lor \overline{x_3} \lor x_4) \land (x_5\lor \overline{x_6} \lor x_9 \lor \overline{x_1}) \)
|
|
|
|
|
|
DNF-SAT = analog\\
|
|
|
\( F = (x_1 \land \overline{x_2} \land x_3) \lor (x_2 \land \overline{x_5} \land x_4) \lor (x_5 \land \overline{x_6} \land x_9 \land \overline{x_1}) \)\\
|
|
|
Es genügt, eine Klausel zu erfüllen \(\Rightarrow\) DNF-SAT\\
|
|
|
\( \Rightarrow \) DNF-SAT ist effizient lösbar.
|
|
|
|
|
|
\section{Einteilung in Klassen}
|
|
|
|
|
|
Sei \( t: \mathbb N \to \mathbb N\)\\
|
|
|
\( DTIME(t) = \{ L \le \Sigma^* \mid \) es gibt eine Turingmaschine M mit \( L(M) = L \) und M macht \(O(t(m))\) Schnitte auf Eingaben der Länge \( n\} \)\\
|
|
|
Analog: \(NTIME(t)\) für NTM.
|
|
|
|
|
|
Analog für Speicherplatz:\\
|
|
|
Hier mit 2-Band Turingmaschine. Dabei darf das Eingabeband nicht verändert werden. Speicherbedarf wird nur in Bezug auf das 2. Band gemessen.\\
|
|
|
Für \( S: \mathbb N \to \mathbb N \)\\
|
|
|
\( DSPACE(s) = \{ L\mid \) es gibt M mit \(L(M)=L\) und M braucht \(O(s(m))\) Platz auf Eingaben der Länge \(n\}\)
|
|
|
|
|
|
\bsp Reguläre Sprachen \( \le DTIME(n) \).\\
|
|
|
Kontextfreie Sprachen in CNF mit CYK-Algorithmus \( \le DTIME(n^3) \) (evtl. $n^4$)
|
|
|
|
|
|
Polynomische Rechenzeit:\\
|
|
|
\( P = \bigcup\limits_{k\ge1} DTIME(n^k) \)\\
|
|
|
\( P = DTIME(n) \cup DTIME(n^2) \cup … \)
|
|
|
|
|
|
Nichtdeterministische polynomische Rechenzeit\\
|
|
|
\( NP = \bigcup\limits_{k\ge 1} NTIME(n^k) \)
|
|
|
|
|
|
\bsp \( HAM \in NP,\) \(SAT, CNF-SAT \in NP \)\\
|
|
|
\( DNF-SAT \in P \)
|
|
|
|
|
|
Offenes Problem: \( HAM, SAT \in P \) ?
|
|
|
|
|
|
In $P$ sind auch Probleme mit Laufzeit \(n^{1000}\). Aber auch mit dieser Laufzeit ist kein Algorithmus für SAT bekannt!
|
|
|
|
|
|
\( \left. \frac{\text{Registermaschienen}}{\text{RAM}} \right\rbrace \) moderne Hardware statt Turingmaschine.\\
|
|
|
Gegenseitige Simulation möglich. Typischer Zeitzuwachs ist dabei ein Faktor von $n^3$ oder $n^4$.\\
|
|
|
D.\,h. $P$ bleibt gleich bei anderer Hardware, genauso NP.
|
|
|
|
|
|
Exponentielle Zeit\\
|
|
|
\( EXP = \bigcup\limits_{k\ge 0} DTIME(2^{n^k}) \)\\
|
|
|
\( NEXP = \) analog mit \(NTIME\)
|
|
|
|
|
|
\underline{Logarithmischer Platz}
|
|
|
|
|
|
\( L = DSPACE(\log n)\)\\
|
|
|
\(NL = NSPACE(\log n)\)
|
|
|
|
|
|
\underline{Polynomischer Platz}
|
|
|
|
|
|
\( PSPACE = \bigcup\limits_{k\ge 0} DSPACE(n^k) \)\\
|
|
|
\( NSPACE = \bigcup\limits_{l\ge 0} NSPACE(n^k) \)
|
|
|
|
|
|
Es gilt:
|
|
|
\begin{enumerate}
|
|
|
\item
|
|
|
\( DTIME(t) \le DSPACE(t) \)\\
|
|
|
pro Schritt kann höchstens ein weiteres Bandfeld beschrieben werden.\\
|
|
|
\( NTIME(t) \le NSPACE(t) \)\\
|
|
|
Folgerungen:\\
|
|
|
\( P \le PSPACE\)\\
|
|
|
\( NP \le NPSPACE\)
|
|
|
\item
|
|
|
\( DTIME(t) \le NTIME(t) \)\\
|
|
|
\( DSPACE(s) \le NSPACE(s) \)\\
|
|
|
Folgerungen:\\
|
|
|
\( P \le NP \)\\
|
|
|
\( EXP \le NEXP \)\\
|
|
|
\( L \le NL \)\\
|
|
|
\( PSPACE \le NPSPACE \)
|
|
|
\item
|
|
|
\( NTIME(t) \le DTIME(2^{O(t)}) \)\\
|
|
|
Folgerung:\\
|
|
|
\( NP \le EXP \)
|
|
|
\item
|
|
|
\( DSPACE(t) \le DTIME(2^{O(t)}) \) (sogar für \(NSPACE(t)\))\\
|
|
|
ohne Beweis\\
|
|
|
Folgerungen:\\
|
|
|
\( PSPACE \le EXP\)\\
|
|
|
\( NL \le P \)
|
|
|
\item
|
|
|
\underline{Satz von Savitch}\\
|
|
|
Sei \(S(m) \ge \log n\)\\
|
|
|
\(NSPACE(s) \le DSPACE(s^2) \)\\
|
|
|
Folgerungen:\\
|
|
|
\( NPSPACE \le PSPACE \)\\
|
|
|
d.\,h. \( PSPACE = NPSPACE \)
|
|
|
\end{enumerate}
|
|
|
|
|
|
Zusammenfassung:\\
|
|
|
\( L \le NL \le P \le NP \le PSPACE \le EXP \le NEXP \)\\
|
|
|
Alle Inklusionen sind offen (ob sie echt sind).\\
|
|
|
z.\,B. \( P \overset{?}{=} NP \leftarrow \) Preis\\
|
|
|
\( L \overset{?}{=} NL \)\\
|
|
|
\( NL \overset{?}{=} P \)\\
|
|
|
\( MP \overset{?}{=} PSPACE\)
|
|
|
|
|
|
Bekannt ist:\\
|
|
|
\( NL \ne PSPACE \)\\
|
|
|
aber \( NL \overset{?}{=} NP \) ist offen.\\
|
|
|
\( P \ne EXP \)\\
|
|
|
aber \( P \overset{?}{=} PSPACE\) ist offen \\
|
|
|
\( NP \ne NEXP \)\\
|
|
|
aber \( NP \overset{?}{=} EXP \) ist offen.\\
|
|
|
offen ist \( L \overset{?}{=} NP \)
|
|
|
|
|
|
\underline{Reduktionen:}
|
|
|
|
|
|
Seien \(A,B \subseteq \Sigma^* \) Sprachen.\\
|
|
|
\underline{A ist auf B reduzierbar}, schreibe \( A \le^P B\), falls es eine in polynomieller Zeit berechenbare Funktion \(f: \Sigma^* \to \Sigma^*\) gibt, so dass gilt:\\
|
|
|
\( \forall x \in \Sigma^*\quad x\in A \leftrightarrow f(x) \in B \).
|
|
|
|
|
|
d.\,h. \( x\in A \Rightarrow f(x) \in B\)\\
|
|
|
und \( x\not\in A \Rightarrow f(x) \not\in B\)
|
|
|
|
|
|
\section{Traveling Salesman (TSP)}
|
|
|
|
|
|
\bsp Traveling Salesman (TSP)\\
|
|
|
Finde kürzeste Rundreise die jede Stadt genau einmal besucht.
|
|
|
|
|
|
\underline{TSP}\\
|
|
|
gegeben: \( n, L, d: \{0,…,n\}^2 \to \mathbb N\)\\
|
|
|
gefragt: gibt es eine Permutationen (=Rundreise)\\
|
|
|
\spa der Länge \( \le L \)\\
|
|
|
dabei ist \( d(i,j) = d(j,i) = \) Abstand von Stadt zu Stadt.
|
|
|
|
|
|
\satz \( HAM \le^P TSP \)\\
|
|
|
\bew gegeben sei \( G = (V,E) \) mit \( \left|V\right| = n\).\\
|
|
|
Definiere:\\
|
|
|
\spa \( d(i,j) = \begin{cases} 1, & \text{falls } (i,j) \in E \\ 2, & \text{sonst} \end{cases} \)
|
|
|
|
|
|
\begin{enumerate}
|
|
|
\item Ein hamilton Kreis ind G liefert eine TSP-Tour der Länge n.
|
|
|
\item Hat G keinen hamilton Kreis, dann benützt \underline{jede} TSP-Tour mindestens eine Kante der Länge 2\\
|
|
|
\(\Rightarrow\) Gesamtlänge \( \ge n+1 \)\\
|
|
|
Dann gilt also\\
|
|
|
\spa \( G\in HAM \Leftrightarrow (n, L, d) \in TSP \).\\
|
|
|
d.\,h. \(f(G) = (n,L,d) \)
|
|
|
\end{enumerate}
|
|
|
|
|
|
\satz Sei \( A \le^P B\).
|
|
|
\begin{enumerate}
|
|
|
\item \( B \in P \Rightarrow A \in P \)
|
|
|
\item \( B \in NP \Rightarrow A \in NP \)
|
|
|
\end{enumerate}
|
|
|
|
|
|
\bew zu 1.\\
|
|
|
Sei \(M_B\) eine Turingmaschine für \(B\) die in polynomieller Zeit arbeitet.\\
|
|
|
Sei \(M_f\) eine Turingmaschine, die die Reduktionsunktion in polynomieller Zeit berechnet.
|
|
|
|
|
|
Sei \(c\in \Sigma^*\) Eingabe für $A$.\\
|
|
|
\( x \to M_f \overset{f(x)}{\rightarrow} M_B \to \{0,1\} \)
|
|
|
|
|
|
Sei $p$ ein Polynom, das die Rechenzeit von $M_f$ beschränkt, z.\,B. \(p(n) = n^k\).\\
|
|
|
Ebenso \(q\) Polynom für \(M_B\), z.\,B. \(q(n) = n^e\)\\
|
|
|
Rechenzeit von \(M_A\) auf x, \(\left|x\right| = n \):\\
|
|
|
\spa\( p(n) + q(\underbrace{p(n)+n}_{\text{max. Länge von }f(x)}) \)\\
|
|
|
Dies ist ein Polynom, alsp \(A\in P\).
|
|
|
|
|
|
\bsp \(n^k + (n^k + n)^l = O(n^{k*l}) \)
|
|
|
|
|
|
\bew zu 2.\\
|
|
|
\(M_B\) nichtdeterministisch \(\Rightarrow M_A \) nichtdeterministisch. Zeit bleibt unverändert.
|
|
|
|
|
|
\defin \(A,B\) heißen (\underline{polynomiell}) \underline{äquivalent}, schreibe \( A \equiv^P B\), falls \(A\le^P B\) und \(B\le^P A\).\\
|
|
|
\lemma \(\equiv^P\) ist Äquivalentzrelation.\\
|
|
|
\bew (R) \(A \equiv^P A\), da \(A\le^P A\) mittels \(f(x)=x\).\\
|
|
|
(S) \( A \equiv^P V \Rightarrow B \equiv^P A \) \(\Box\)\\
|
|
|
(T) \( A\le^P B\) und \(B \le^P C \Rightarrow A\le^P C \)
|
|
|
|
|
|
Sei \(A\le^P B \) mittels \(f\) und \(B\le^P C\) mittels \(g\)\\
|
|
|
Definiere \(h(x) = g(f(x)) \).\\
|
|
|
Rechenzeit für \(h\) ist Polynom \(\Box\)
|
|
|
|
|
|
\defin Sei \(A\subseteq \Sigma^*\).\\
|
|
|
A ist \underline{NP-hart}, falls \( \forall L \in NP \quad L \le^P A\).\\
|
|
|
A heißt \underline{NP-Vollständig}, falls $A$ NP-Hart ist und \( A \in NP \)
|
|
|
|
|
|
\satz Sei \(A\) NP-Vollständig.\\
|
|
|
\(A\in P \Rightarrow P = NP \).\\
|
|
|
\bew Sei \(L\in NP\). Zeige: \(L\in P\)\\
|
|
|
Da \(A\) NP-vollständig ist, gilt: \( L\le^P A \).\\
|
|
|
Nach obigem Satz: \( A\in P\Rightarrow L \in P \)
|
|
|
|
|
|
\satz Sind \(A,B\) NP-volständig, dann ist \( A\equiv^P B\).
|
|
|
|
|
|
\textcolor{darkblue}{\underline{Satz von Cook (1971)}}\\
|
|
|
\(SAT\) ist NP-Vollständig.\\
|
|
|
\bew \(SAT\in NP\)\\
|
|
|
Sei \(M = (Z,\Sigma,\Gamma,\delta,Z_a,Z_v,\Box)\) eine NTM mit Rechenzeit \(p(n)\) mit \(L=L(M)\).\\
|
|
|
Sei \(Z = \{ Z_0,Z_1,…,Z_k\}, \underset{\subseteq \Sigma}{\Gamma} = \{a_1,…,a_m\} \)
|
|
|
|
|
|
Sei \(x\in\Sigma^*\) Eingabe für $M$. Gebe Reduktionsfunktion $f$ an, so dass \(f(x) = F_x\) eine boolesche Formel ist, so dass gilt:\\
|
|
|
\spa \(x\in L(M) \Leftrightarrow F_x \in SAT \)\\
|
|
|
\spa \(\left|x\right| = n\)
|
|
|
|
|
|
Variablen von \(F_x\):\\
|
|
|
\(zust_{t,z}, t=0,1,…,P(n), z\in Z\)\\
|
|
|
\spa (Intuitiv: \(=1\), falls M zum Zeitpunkt $t$ im Zustand $z$, sonst 0)\\
|
|
|
\(pos_{t,i}, t=0,1,…,p(n),i \)\\
|
|
|
\spa (Intuitiv: \(=1\), falls der Lese/Schreibkopf von M zum Zeitpunkt $t$ auf Feld $i$ steht)\\
|
|
|
\(band_{t,i,q}, t = 0,1,…,P(n), i=-p(n),...,p(n), a \in \Gamma \)
|
|
|
\spa (Intuitiv:\(=1\), falls auf dem Band von M zum Zeitpunkt $t$ auf Feld $i$ das Zeichen $a$ steht, 0 sonst)
|
|
|
|
|
|
\(F_x\) setzt sich zusammen aus\\
|
|
|
\spa \( F_x = R\land A \land U_1 \land U_2 \land E\)
|
|
|
R ist die Randbedingung.
|
|
|
|
|
|
Zu jedem Zeitpunkt $t$ ist genau eine Variable von \(zust_{t,z_0}, …, zust_{t,z_k} \) wahr.
|
|
|
Ebenso von \( pos_{t,-p(m),…,p(m)} \)
|
|
|
|
|
|
Variable \(y_1,…,y_n\)\\
|
|
|
\( G(y_1,…,y_n) = \begin{cases} 1, & \text{falls genau eine der Variable } y_i = 1 \text{ ist}\\0, &\text{sonst}\end{cases} \)
|
|
|
|
|
|
\( G = y_1,…,y_n) = ( \bigvee\limits_{i=1}^n y_i ) \land ( \bigwedge\limits_{1\le i\le j\le n} \overline{y_i \land y_j} ) \)
|
|
|
|
|
|
1. Teil heißt: \(\ge 1\) Variablen ist \(1\)\\
|
|
|
2. Teil heißt: keine 2 Variablen sind 1 \(\equiv \le 1\) Variable ist 1
|
|
|
|
|
|
Damit\\
|
|
|
\( R = \bigwedge\limits_{t=0}^{p(n)} \left( G( zust_{t,t_0}, …, zust_{t,t_k} ) \land G(pos_{t,-p(n)},…,pos_{t,p(n)}) \land \bigwedge\limits_{i=-p(n)}^{p(n)} G(band_{t,i,a},…,band_{t,i,a_m}) \right) \)\\
|
|
|
\( \left|R\right| = O\left(p(n) * (1 + (2*p(n))^2 + 2 * p(n) * 1) \right) \)\\
|
|
|
\( = O(p^3(n)) \)
|
|
|
|
|
|
\(A\), die Anfangsbedingung beschreibt die Variablen zum Zeitpunkt \(t=0\).\\
|
|
|
\( A = zust_{0,Z_0} \land pos_{0,1} \land \left( \bigwedge\limits_{i=-p(n)}^{0} band_{0,1,\Box} \land \bigwedge\limits_{i=1}^{n} band_{0,i,x_i} \land \bigwedge\limits_{i = n+1}^{p(n)} band_{0,i,\Box} \right)\)\\
|
|
|
\( \left|A\right| = O(p(n)) \)
|
|
|
|
|
|
\( \ddot U_1 = \) Beschreibt den Übergang von $t$ nach \(t+1\) an der Stelle, an der der Lese/Schreib-Kopf steht.\\
|
|
|
\( = \bigwedge\limits_{t=0}^{p(n)-1} \bigwedge\limits_{z\in Z} \bigwedge\limits_{i=-p(n)}^{p(n)} \bigwedge\limits_{a\in\Gamma} \left( (zust_{t,Z} \land pos_{t,i} \land band_{t,i,a} ) \to \bigvee\limits_{Z',a',d} ( zust_{t+1,Z'} \land pos_{t+1,i+d} \land band_{t+1,i,a'} ) \right)\)\\
|
|
|
\( (Z',a',d) \in \delta(Z,a) \) mit \( d = \begin{cases} 1 & \text{für R} \\ 0 & \text{für N} \\ -1 & \text{für L} \end{cases} \)
|
|
|
|
|
|
\( \left|\ddot U_1\right| = O\left( p(n) * 1 * (2 *p(n)) * 1 * 1 \right) = O\left(p^2(n)\right) \)
|
|
|
|
|
|
\(\ddot U_2\) beschreibt die restlichen Übergänge.\\
|
|
|
\( \ddot U_2 = \bigwedge\limits_{t=0}^{p(n)} \bigwedge\limits_{i=-p(n)}^{p(n)} \bigwedge\limits_{a\in\Gamma} \left( \neg pos_{t,i} \land band_{t,i,a} \to band_{t+1,i,a} \right) \)
|
|
|
\( \left|\ddot U_2\right| = O\left(p^2(n)\right) \)
|
|
|
|
|
|
E beschreibt das Ende, dass M akzeptiert\\
|
|
|
\( E = \bigvee\limits_{t=1}^{p(n)} zust_{t,Z_a} \)\\
|
|
|
\( \left|E\right| = O\left(p(n)\right) \)
|
|
|
|
|
|
\( F_x = R\land A\land \ddot U_1 \land \ddot U_2 \land E \)\\
|
|
|
\( \left|F_x\right| = O\left(p(n)^3\right) \)
|
|
|
|
|
|
Dann gilt:\\
|
|
|
zu jeder akzeptierenden Rechnung von \(M(x)\) gibt es eine zugehörige Belegung der Variablen von \(F_x\), die \(F_x\) erfüllt, und umgekehrt.
|
|
|
|
|
|
Es gilt also: \(M(x)\) hat gleich viele akzeptierende Rechnungen wie \(F_x\) erfüllende Belegungen.\\
|
|
|
Insbesondere gilt also:\\
|
|
|
\spa \( x\in L(M) \Leftrightarrow F_x \in SAT \quad \Box\)
|
|
|
|
|
|
Um von einem weiteren Problem A zu zeigen, dass A NP-vollständig ist, genügtves jetzt zu zeigen\\
|
|
|
\spa \( SAT \le^P A \) (und \(A\in NP\))\\
|
|
|
da dann für \( L\in NP\) gilt:\\
|
|
|
\spa \( L \le^P SAT \) und \( SAT \le^P A \Rightarrow L \le^P A\).
|
|
|
|
|
|
\underline{Cook} SAT ist NP-Vollständig
|
|
|
|
|
|
\satz Sei $A$ NP-Vollständig und \(B\in NP\).\\
|
|
|
Dann gilt: $B=$ NP-Vollständig \( \Leftrightarrow A \le^P V \)
|
|
|
|
|
|
\( KNF-SAT = \{ F \in SAT\mid F \text{ ist in KNF} \} \)
|
|
|
|
|
|
\( k-SAT = \{ F \in KNF-SAT \mid \) jede Klausel von $F$ hat $\le 3$ Literale \( \} \)
|
|
|
|
|
|
\satz 3-SAT ist NP-Vollständig.\\
|
|
|
\bew Zeige \( SAT \le^P 3-SAT \)\\
|
|
|
\bsp Sei $F$ boolsche Formel.\\
|
|
|
\( F = \left(( x_1 \lor \overline{x_3}) \land x_4 \right) \lor ( \overline{x_2} \land x_3) \)
|
|
|
|
|
|
\begin{enumerate}[1{. Schritt:}]
|
|
|
\item Bringe alle Negationszeichen nach innen \( \neg(x_1\lor \overline{x_2}) \equiv (\overline{x_1}\land x_2)\)
|
|
|
\item nehme neue Variablen \( y_1,y_2,…\) und ordne jedem Gatter eine Variable zu
|
|
|
\item Definiere G\\
|
|
|
\( G = (y_1 \leftrightarrow (x_1\lor \overline{x_3})) \land (y_2 \leftrightarrow (y_1 \land x_4)) \land (y_3 \leftrightarrow (\overline{x_2} \land x_3)) \land (y_4 \leftrightarrow (y_2 \lor y_3)) \land y_4 \)\\[3mm]
|
|
|
Dann gilt: \( F \in SAT \Leftrightarrow G \in SAT \)\\[3mm]
|
|
|
\( x_1 = 1, x_2 = 0, x_3 = 1, x_4 = 1 \)\\
|
|
|
\( y_1 = 1, y_2 = 1, y_3 = 1, y_4 = 1 \)
|
|
|
\item forme einzelne Klammern in KNF um:\\
|
|
|
\( a \leftrightarrow (b\lor c) \equiv (a\lor \overline{b}) \land (\overline{a}\lor b\lor c) \land (a \lor \overline{c}) \)\\
|
|
|
\( a \leftrightarrow (b\land c)\equiv (\overline{a}\lor b)\land (a\lor\overline{b}\lor\overline{c})\land(\overline{a}\lor c)\)
|
|
|
\end{enumerate}
|
|
|
|
|
|
Dann ist $G$ in 3-KNF. \( \blacksquare \)\\
|
|
|
Es gilt: 2-SAT \(\in P\)
|
|
|
|
|
|
Not-all-equal-SAT, kurz: NAE-SAT
|
|
|
|
|
|
gegeben: $F$ in 3-KNF\\
|
|
|
gefragt: gibt es eine erfüllende Belegung für $F$, so dass in keiner Klausel alle Literale den Wert 1 haben.
|
|
|
|
|
|
\( F = (x_1 \lor \overline{x_2}) \land (\overline{x_1} \lor x_2) \)
|
|
|
|
|
|
\satz $NAE-SAT$ ist NP-Vollständig\\
|
|
|
\bew $NAE-SAT \in NP$:\\
|
|
|
wähle nicht-deterministisch Belegung a und teste dass jede Klausel erfüllt ist und nicht alle 3 Literale Wert 1 haben.
|
|
|
|
|
|
Zeige \( SAT \le^P NAE-SAT \)\\
|
|
|
Sei $F$ beliebige Formel und $G$ die oben konstruierte in 3-KNF.\\
|
|
|
Es gilt: eine erfüllbare Belegung von $G$ erfüllt nicht alle Literale in Klauseln mit 3 Literalen.
|
|
|
\begin{itemize}
|
|
|
\item \( \overline{a} \lor b\lor c: \) haben $b$ oder $c$ den Wert 1, dann muss $a=1$ sein, da \( a\leftrightarrow a\lor b\)
|
|
|
\item ist \(b=c=0\), dann ist \(a=0\), also \(\overline{a} = 1\)
|
|
|
\end{itemize}
|
|
|
\(a\lor \overline{b}\lor\overline{c}: \) hat \(\overline{b}\) oder \(\overline{v}\) Wert 1, dann ist \( a=0\), da \(a\leftrightarrow(n\lor c\).
|
|
|
\begin{itemize}
|
|
|
\item ist \(\overline{b} = \overline{c} = 0\), dann ist \(a = a\)
|
|
|
\end{itemize}
|
|
|
Für die Klauseln mit 2 Literalen nehme neue Variable $Z$ hinzu und bringe $Z$ in die Klauseln ein:\\
|
|
|
\( a\lor\overline{b} \to a \lor \overline{b} \lor z \)\\
|
|
|
\( a\lor\overline{c} \to a \lor \overline{c} \lor z \)
|
|
|
|
|
|
Sei \(H\) die so entstehende Formal.\\
|
|
|
Dann gilt: \( F\in SAT\leftrightarrow G \in 3-SAT\)\\
|
|
|
\( F\in SAT\leftrightarrow G \in NAE-SAT \).
|
|
|
|
|
|
"\(\Rightarrow\)": Sei \( a = (a_1,…a_n) \) eine erfüllende Belegung von $G$.\\
|
|
|
Dann wähle $z=0$.\\
|
|
|
Dann ist \((a_1,…a_n,0)\) erfüllende Belegung von $H$.
|
|
|
|
|
|
"\(\Leftarrow\)" Sei \( (a_1,a_2,…,a_n,a_{n+1}) \) erfüllende Belegung von $H$ im NAE-Sinn.\\
|
|
|
\begin{enumerate}[1{. Fall:}]
|
|
|
\item
|
|
|
\( a_{n+1} = 0 \) dann ist, \( a = (a_1,…,a_n)\) erfüllende Belegung von $G$
|
|
|
\item \(a_{n+1} = 1 \)
|
|
|
Es ist auch \(( \overline{a_1},\overline{a_2},…,\overline{a_n},\overline{x_{n+1}})\) einer erfüllende Belegung von $H$ im NAE-Sinn.\\
|
|
|
\((0,0,1)\to(1,1,0)\)\\
|
|
|
Jetzt ist \(t=0\). Dann nach Fall 1.
|
|
|
\end{enumerate}
|
|
|
|
|
|
NP-Vollständig sind: \(SAT, 3-SAT, NAE-SAT \)
|
|
|
|
|
|
\section{k-Färbbarkeit}
|
|
|
|
|
|
gegeben: \( G = (V,E) \) ungerichtet\\
|
|
|
gefragt: \( \exists f: V \to \{ 1, …, k\} \) mit \( f(n) \ne f(v) \quad \forall (u,v) \in E\)
|
|
|
|
|
|
\satz 3-Färbbarkeit ist NP-Vollständig\\
|
|
|
\bew[ in NP] gebe nichtdeterministisch jedem Knoten eine der 3 Farben. Dann prüfe, ob es eine 3-Färbung ist.\\
|
|
|
Beachte: Suchraum aller Zuordnungen von Farben zu V hat größe \(3^n\)
|
|
|
|
|
|
Es gibt \(k^n\) Funktionen \(f: V\to \{1,…,k\}\)
|
|
|
|
|
|
Zeige: \(NAE-SAT \le^P \) 3-Färbbarkeit.\\
|
|
|
gegeben: $F$ in \(3-KNF\)\\
|
|
|
Konstruiere einen Graph $G$, so dass \( F\in NAE-SAT \Leftrightarrow G \) 3-Färbbar
|
|
|
|
|
|
\bsp \( F = ( x_1 \lor \overline{a_x} \lor x_3 )\land … = c_1 \land c_2 \land … \land c_m \)
|
|
|
|
|
|
\begin{enumerate}[1)]
|
|
|
\item
|
|
|
Sei \(F\in NAE-SAT\) und \( a=(a_1,a_2,…,a_n)\) eine erfüllende Belegung für $F$. Dann ist G 3-Färbbar.\\
|
|
|
$x_i$ Farbe $a_i$ und $\overline{x_i}$ Farbe $\overline{a_i}$.\\
|
|
|
Bei den Klauseln: pro $\triangle$:
|
|
|
\begin{itemize}
|
|
|
\item wähle ein Literal mit Wert 1 und gebe Knoten die Farbe 1
|
|
|
\item wähle ein Literal mit Wert 0 und gebe Knoten Farbe 0
|
|
|
\item Knoten vom dritten Literal bekommt Farbe 2.
|
|
|
\end{itemize}
|
|
|
\item Sei G 3-Färbbar:\\
|
|
|
Der Wurzelknoten habe Farbe 2 (sonst permutiere Farben in $G$).\\
|
|
|
Sei $a_i$ die Farbe von $x_i$ im oberen Teil, d.\,h. \( a_i\in\{0,1\}\). Belege Variable \(x_i\) ind $F$ mit $a_i$.
|
|
|
Dann ist \( a = (a_1,…,a_n)\) eine erfüllende Belegung vonm $F$.\\
|
|
|
In Klausel-\(\triangle\) gibt es alle 3 Farben. Literal mit Farbe 0 hat Wert 0 in der Klausel, Literal mit Farbe 1 hat Wert 1 in der Klausel.\\
|
|
|
\(\Rightarrow F\) ist erfüllt.
|
|
|
\end{enumerate}
|
|
|
|
|
|
$G$ bipartit.\\
|
|
|
\( \Leftrightarrow G\) 2-färbbar\\
|
|
|
\( \Leftrightarrow\) alle Kreise in $G$ haben gerade Länge.
|
|
|
|
|
|
Algeimein für 2-färbbar:
|
|
|
\begin{enumerate}[1)]
|
|
|
\item starte mit beliebigem Knoten $v$ und gebe $v$ Farbe 1
|
|
|
\item Wiederhole:\\
|
|
|
\spa gebe Nachbarn von $v$ andere Farbe, wähle nächstes $v$.\\
|
|
|
Trifft man dabei auf einen bereits gefärbten Knoten mit anderer Farbe als er jetzt bekommen sollte, dann ist $G$ nicht2-färbbar.
|
|
|
\(\Rightarrow\) 2-Färbbarkeit \( \in P\)
|
|
|
\end{enumerate}
|
|
|
|
|
|
\satz $HAM$ ist NP-Vollständig\\
|
|
|
Zeige: $3-SAT \le^P HAM$\\
|
|
|
Gegeben: \( F(x_1,…,x_n) = c_1\land c_2 \land … \land c_n \)\\
|
|
|
Konstruiere einen Graph $G$, so dass \( F\in 3-SAT \Leftrightarrow G\in HAM\)
|
|
|
|
|
|
G: Für jede Variable $x_i$ konstruiere folgenden Teilgraph.
|
|
|
|
|
|
Soweit hat der Graph $2^n$ ham. Kreise und diese lassen sich je einer Belegung der Variablen von $F$ zuordnen.
|
|
|
|
|
|
\bsp \( F = (x_1 \lor \overline{x_2} \lor \overline{x_3}) \land (x_2 \lor \overline{x_3}) \)
|
|
|
|
|
|
\begin{enumerate}[1)]
|
|
|
\item
|
|
|
Sei $F\in 3-SAT$ und $a=(a_1,…,a_n)$ eine erfüllende Belegung für $F$.\\
|
|
|
Dann hat $G$ einen ham. Kreis:\\
|
|
|
gehe bei Teilgraph für $x_i$ nach links, falls $a_i = 0$ und nach recht, falls $a_i=1$ ist.\\
|
|
|
\begin{itemize}
|
|
|
\item Kommt $x_i$ in $C_j$ vor und ist $a_i=1$ und $C_j$ noch nicht besucht worden, dann verzweige zu Klauselknoten $C_j$.
|
|
|
\item kommt $\overline{x_i}$ in $C_j$ vor und ist $a_i = 0$ und $C_j$ noch nicht besucht, dann verzweige zu Knoten für $C_j$.
|
|
|
\end{itemize}
|
|
|
Da $a$ $F$ erfüllt, wird so jeder Klauselknoten erreicht.
|
|
|
\item
|
|
|
Sei $G \in HAM$.\\
|
|
|
Es gibt nur ham. Kreise wie unter 1) beschrieben und diese entsprechen dann erflüllender Belegung von $F$.
|
|
|
\end{enumerate}
|
|
|
|
|
|
\( HAM_{ger} \le^P HAM_{unger} \)\\
|
|
|
Gegeben: $G$ gerichtet.\\
|
|
|
Konstruiere $G'$ ungerichtet, so dass:\\
|
|
|
\( G \in HAM_{ger} \Leftrightarrow G' \in HAM_{unger} \)
|
|
|
\begin{enumerate}[1)]
|
|
|
\item Ein ham. Kreis in $G$ liefert direkt einen ham. Kreis in $G'$.
|
|
|
\item Ham. Kreise in $G'$ müssen die Richtun gvon $G$ einhalten (oder komplett in Gegenrichtung). Andernfalls bleibt man stecken, z.\,B. bei $v^1$.
|
|
|
\end{enumerate}
|
|
|
|
|
|
\section{Unabhängige Knotenmenge (Independent Set (IS))}
|
|
|
|
|
|
gegeben: \( G = (V,E), k \)\\
|
|
|
gefragt: \( \exists I \subseteq V, \left|I\right| \ge k \)\\
|
|
|
innerhalb von $I$ gibt es keine Kanten.:w
|
|
|
|
|
|
\( IS \in NP \): rate $I\subseteq V, \left|I\right|=k $\\
|
|
|
prüfe, ob $I$ unabhängig
|
|
|
|
|
|
Deterministisch: durchlaufe alle $I\subseteq V$ mit $\left|I\right|=k$\\
|
|
|
Es gibt $\binom{n}{k}$ solche Teilmengen.\\
|
|
|
\(n^{\frac n2} \le \binom{n}{k}\le n^k\)
|
|
|
|
|
|
\( 3-SAT \le^P IS \)\\
|
|
|
Sei \( F(x_1,…,x_n) = c_1 \land c_2 \land … \land c_n\) in \(3-KNF\)\\
|
|
|
Konstruiere Graph $G$ und $k$, so dass gilt \(F\in 3-SAT \Leftrightarrow (G,k) \in IS\)
|
|
|
|
|
|
\bsp \( F = (x_1\lor x_2\lor x_3)\land(\overline{x_1}\lor \overline{x_2}\lor x_3) \land ( \overline{x_1}\lor x_2\lor \overline{x_3}) \)\\
|
|
|
Verbinde zwischen allen \(C_i\) und \(C_j\) \( i\ne j\) komplimentäre Literale
|
|
|
|
|
|
Beobachtung: eine unabhängige Menge $I$ in $G$ kann aus jedem Klauseldreieck höchstens 1 Knoten haben \(\Rightarrow \left|I\right| \le m \)\\
|
|
|
\beh \( F \in 3-SAT \Leftrightarrow (G,m) \in IS \).\\
|
|
|
\('\Rightarrow'\) Sei \( a=(a_1,…,a_n)\) erfüllende Belegung von $F$.\\
|
|
|
Definiere $I$: wähle aus jedem Klausel-\(\triangle\) einen Knoten, dessen Literal Wert 1 hat.\\
|
|
|
Im \bsp \( a=(1,0,0)\)\\
|
|
|
\( \rightarrow I = \{x_1 \text{ aus } C_1, \overline{x_2}\text{ aus }C_2, \overline{x_3}\text{ aus } C_3 \}\)\\
|
|
|
Dann ist $I$ unabhängig, da nie $x_i$ und $\overline{x_i}$ ausgewählt wurden (sonst wäre $a$ nicht erfüllbar) und nur diese durch Kanten verbunden sind.
|
|
|
|
|
|
\('\Leftarrow'\) Sei $I$ unabhängig, \(\left|I\right|=m\).\\
|
|
|
Dann muss $I$ nach obiger Beobachtung aus \underline{jedem} Klausel-\(\triangle\) genau einen Knoten haben.\\
|
|
|
Konstruiere Belegung $a$ für F:\\
|
|
|
Wähle aus Klausel-\(\triangle\) für \(C_i\) das Literal das in $I$ ist und gebe Wert 1.\\
|
|
|
Noch nicht belegte Variablen können jetzt beliebig belegt werden. Diese Belegung erfüllt $F$, da keine komplementären Literale auftauchen.
|
|
|
|
|
|
\section{Clique}
|
|
|
|
|
|
gegeben: \( G = (V,E), k\)\\
|
|
|
gefragt: \( \exists C \subseteq V, \left|C\right| \ge k \)\\
|
|
|
so dass je 2 Knoten in $C$ durch eine Kante verbunden sind.
|
|
|
|
|
|
Clique \(\in NP\): rate \( C \subseteq V, \left|C\right|=k\) prüfe, ob $C$ Clique ist.\\
|
|
|
\( IS =^P \) Clique\\
|
|
|
Sei \(G,k\) Eingabe für $IS$.\\
|
|
|
Konstruiere $G',k'$, so dass \( (G,k) \in IS \Leftrightarrow (G',k') \in\) Clique.
|
|
|
|
|
|
Der \underline{Komplementgraph von G} ist \( \overline{G} = (V,\overline{E})\)\\
|
|
|
D.\,h. \( \overline{E} = \{ (a,v) \mid (u,v) \not\in E \} \)\\
|
|
|
Dann gilt: \( (G,k) \in IS \Leftrightarrow (\overline{G},k) \in \) Clique
|
|
|
|
|
|
\section{Knotenüberdeckung (Vortex Cover (VC))}
|
|
|
|
|
|
gegeben: \( G = (V,E), k\)\\
|
|
|
gefragt: \( \exists C\subseteq V, \left|C\right| \le k\), so dass \underline{jede} Kante in G mindestens einen Endpunkt in C hat.
|
|
|
|
|
|
\( VC \in NP\): rate \( C \subseteq V, \left|C\right|=k\) prüfe, ob $C$ cover ist.\\
|
|
|
\( IS \le^P VC\)\\
|
|
|
Sei $G,k$ Eingabe für $IS$.\\
|
|
|
Ziel: konstruiere \(G',k'\), so dass gilt: \( (G,k) \in IS \Leftrightarrow (G',k') \in VC \)\\
|
|
|
D.\,h. \( G' = G \) und \( C = V-I = \overline{I} \)\\
|
|
|
Dann gilt: \( (G,k) \in IS \Leftrightarrow (G,n-k) \in VC \)
|
|
|
|
|
|
\section{Dominating Set (DS)}
|
|
|
|
|
|
Gegeben: \( G= (V,E), k\)\\
|
|
|
Gefragt: \( \exists D \subseteq V, \left|D\right|\le k\)\\
|
|
|
so dass für jeden Knoten $v\in V$ gilt: $v$ oder ein Nachbar von $v$ ist in $D$.
|
|
|
|
|
|
\( VC \le^P DS:\)\\
|
|
|
Sei $G,k$ eine Eingabe für $VC$.\\
|
|
|
Ziel: konstruiere $G'$, so dass $(G,K)\in VC \Leftrightarrow (G',k) \in DS$
|
|
|
|
|
|
\includegraphics{bilder/ds-vc.pdf}
|
|
|
|
|
|
Für jede Kante $(u,v)$ in $G$ führe neuen Knoten $K_{(u,v)}$ ein und Kanten $(u,K_{(u,v)})$ und $(v,K_{(u,v)})$ (ungerichtet).
|
|
|
|
|
|
\('\Rightarrow'\) Sei $C$ $VC$ in $G$, d.\,h. für jede Kante $(u,v) \in E$ ist $u\in C$ oder $v\in C$.
|
|
|
|
|
|
\(\Rightarrow\) der neue Knoten $K_{u,v}$ hat einen Nachbarn in $C$\\
|
|
|
\(\Rightarrow\) $C$ ist d.s. in $G'$.\\
|
|
|
\('\Leftarrow'\) Sei $D$ d.s. in $G'$\\
|
|
|
\includegraphics{bilder/ds-vc2.pdf}
|
|
|
Enthält $D$ neue Knoten $K_{u,v}$ dann ersetze $K_{u,v}$ durch $u$ in $D$. Danach entsteht $D'$. Dann ist $D'$ (immer noch d.s.).\\
|
|
|
Dann gilt \( \left|D'\right| \le k\) und $D'$ ist V.C. in $G$:\\
|
|
|
wäre für Knate $(u,v)$ weder $u\in D'$ noch $v\in D'$, dann hätte $K_{u,v}$ keinen Nachbarn in $D'$.\\
|
|
|
Dann wäre $D'$ kein D.S. \Lightning
|
|
|
|
|
|
\section{Subset Sum}
|
|
|
|
|
|
Gegeben: \(a_1,a_2,…,a_n,b\).\\
|
|
|
Gefragt: \( \exists I \le \{ 1,2,…,n\} \quad \sum\limits_{i\in I} a_i - b \)
|
|
|
|
|
|
\bsp \(1,2,5,7,9,\underbrace{14}_{=b} \in \) Subset Sum\\
|
|
|
\( 4 \not\in \) Subset Sum
|
|
|
|
|
|
\( \in NP:\) rate $I$, teste Summe.\\
|
|
|
Subset Sum ist $NP$-Vollständig.\\
|
|
|
$3-SAT \le^P$ Subset Sum:
|
|
|
|
|
|
Sei \( F(x_1,…x_n) = C_1 \land … C_m \) .\\
|
|
|
\( b = \underbrace{33…3}_{m}{\color{Orange}|} \underbrace{11…1}_{n} \) dezimal.
|
|
|
|
|
|
\bsp \( F = (x_1 \lor \overline{x_2} \lor x_3) \land (\overline{x_1} \lor x_2 \lor x_4) \land (\overline{x_2} \lor \overline{x_4} \lor x_5) \)\\
|
|
|
Zahlen \( y_1, …, y_n \) für \( x_1,…,x_n \)\\
|
|
|
\( y_1 = \overbrace{100}^{m=3} {\color{Orange}|} \overbrace{1000}^{n=5} \)\\
|
|
|
$x_1$ kommt in $C_1$ vor\\
|
|
|
$X_1$ kommt nicht in $C_2,C_3$ vor.
|
|
|
|
|
|
\( y_2 = 010 {\color{Orange}|} 01000 \)\\
|
|
|
\( y_3 = 100 {\color{Orange}|} 00100 \)\\
|
|
|
\( y_4 = 010 {\color{Orange}|} 00010 \)\\
|
|
|
\( y_5 = 001 {\color{Orange}|} 00001 \)
|
|
|
|
|
|
Analog \( Z_1,…,Z_n \) für \( \overline{x_1},…,\overline{x_n}\)\\
|
|
|
\( Z_1 = 010 {\color{Orange}|} 10000 \)\\
|
|
|
\( Z_2 = 101 {\color{Orange}|} 01000 \)\\
|
|
|
\( Z_3 = 000 {\color{Orange}|} 00100 \)\\
|
|
|
\( Z_4 = 001 {\color{Orange}|} 00010 \)\\
|
|
|
\( Z_5 = 000 {\color{Orange}|} 00001 \)
|
|
|
|
|
|
Füllzahlen \( f_1,…f_m, g_1,…g_m \)\\
|
|
|
\( f_1 = g_1 = 100 {\color{Orange}|} 00000 \)\\
|
|
|
\( f_2 = g_2 = 010 {\color{Orange}|} 00000 \)\\
|
|
|
\( f_3 = g_3 = 001 {\color{Orange}|} 00000 \)
|
|
|
|
|
|
Es gibt nie Überträge, da im vorderen Teil kann man höchstens auf 3 Einsen kommen pro Klauselspalte mit $y-$ und $z-$Zahlen + max. 2 Einsen mit $f-$ und $g-$Zahlen.\\
|
|
|
\(\Rightarrow\) Summe pro Klauselspalte \(\le 5\)\\
|
|
|
Im hinteren Teil höchstens 2 Einsen pro Spalte.
|
|
|
|
|
|
\('\Rightarrow'\) Sei \( a = (a_1,…,a_n)\) erfüllende Belegung von $F$.\\
|
|
|
Wähle $y_i$, falls $a_i = 1$,\\
|
|
|
wähle $z_i$, falls $a_i = 0$\\
|
|
|
Summe ergibt \( s_1s_2…s_m 11…1 \), wobei \(s_i \in \{1,2,3\} \), da in jeder Klausel $\ge 1$ Literal den Wert 1 hat.\\
|
|
|
Dann wähle passende Füllzahlen um auf $b$ zu kommen.\\
|
|
|
D.\,h. $f_i$ und $g_i$, falls $s_i=1$ und $f_i$, falls $s_i=2$.\\
|
|
|
\('\Leftarrow'\) Habe Subset Sum Problem eine Lösung.\\
|
|
|
Wegen 1-er Block in $b$ muss für jedes $i$ entweder $y_i$ oder $z_i$ in der Lösung sein.\\
|
|
|
\defin \(a_i=1\), falls $y_i$ in Lösung,\\
|
|
|
$a_i = 0$, falls $z_i$ in Lösung.
|
|
|
|
|
|
Dann ist $a=(a_1,…,a_n)$ erfüllende Belegung von F:\\
|
|
|
Da im vorderen Teil mit den Füll-Zahlen maximal 2 erreicht werden kann, muss die Summe der ausgewählten $y-$ und $z-$Zahlen $\ge 1$ je Klauselspalte sein.\\
|
|
|
\(\Rightarrow\) nach Konstruktion enthält also jede Klausel $\ge 1$ erfülltes Problem.
|
|
|
|
|
|
\section{Knapsack (Rucksack)}
|
|
|
|
|
|
Gegeben: \( s_1,…,s_n, \ , w_1,…,w_n, \ , s, w \)\\
|
|
|
Gefragt: \( \exists I \subseteq \{ 1,…,n\} \)\\
|
|
|
\( \sum\limits_{i\in I} s_i \le S\) und \( \sum\limits_{i\in I} w_i \ge W \)\\
|
|
|
\( \in NP \)\\
|
|
|
Knapsack ist $NP$-Vollständig. Subset Sum $\le^P$ Knapsack.
|
|
|
|
|
|
Sei \(a_1,…,a_n,b\) Eingabe für Subset Sum. Konstruiere Eingabe für Knapsack:\\
|
|
|
\( S_i = a_i \ , S=b\)\\
|
|
|
\( w_i = a_i \ , W=b\)\\
|
|
|
Dann ist \( \sum\limits_{i\in I} a_i = b \Leftrightarrow \sum\limits_{i\in I} a_i \le b \) und \( \sum\limits_{i\in I} a_i \ge b\)
|
|
|
|
|
|
\section{Partition}
|
|
|
|
|
|
Gegeben: \( a_1,…a_n\)\\
|
|
|
Gefragt: \( \exists I \subseteq \{ 1,…,n\} \)\\
|
|
|
\( \sum\limits_{i\in I} a_i = \sum\limits_{i\not\in I} a_i\)\\
|
|
|
\( \in NP\)-Vollständig
|
|
|
|
|
|
Subset Sum \( \le^P\) Partition.
|
|
|
|
|
|
Sei \(a_1,a_2, …, a_n,b\) Eingae für Subset Sum.\\
|
|
|
Sei \( A = \sum\limits_{i=1}^n a_i\)\\
|
|
|
Sei \( I \subseteq \{1,…,n\}i \) mit \( \sum\limits_{i\in I} a_i = b\)
|
|
|
|
|
|
\includegraphics{bilder/partition.pdf}
|
|
|
|
|
|
Dann ist \( \sum\limits_{i\in I} a_i + A-b = \sum\limits_{i\not\in I} a_i + b\)
|
|
|
|
|
|
D.\,h. Eingabe \( a_i,…,a_n,b,A-b \) für Partition hat Lösung.\\
|
|
|
\underline{Aber}: die hat immer die Lösung: \( \underbrace{\sum\limits_{i=1}^n a_i}_{=A} = \underbrace{b+(A-b)}_{=A} \)
|
|
|
|
|
|
Stattdessen: \( a_i,…,a_n, b+1, A-b+1 \)\\
|
|
|
Dann ist \( \sum\limits_{i\in I} a_i + (A-b+1) = \sum\limits_{i\not\in I} a_i + (b+1) \)
|
|
|
|
|
|
Aber \( \sum\limits_{i=1}^n a_i = A \not= (b+1) + (A-b+1) = A+2 \)
|
|
|
|
|
|
\('\Leftarrow'\) Sei $I$ eine Lösung für das Partitionsproblem $a_1,…,a_n,\underbrace{b+1}_{=a_{n+1}}, \underbrace{A-b+1}_{=a_{n+2}} $\\
|
|
|
Da \( (b+1) + (A-b+1) = A+2 > A\) kann nur eine von beiden Zahlen zu $I$ gehören. Sei o.\,B.\,d.\,A.\footnote{o.\,B.\,d.\,A.: ohne Beschränkung der Allgemeinheit} sei $n+2 \in I$ (sonst betrachte $\overline{I}$).
|
|
|
|
|
|
Es gilt aber:\\
|
|
|
\( \sum\limits_{i\in I} a_i + A-b+1 = \sum\limits_{i\not\in I} a_i+b+1 \)\\
|
|
|
\(\Rightarrow \sum\limits_{i\in I} a_i + \underbrace{A - \sum\limits_{i\not\in I} a_i}_{ =\sum\limits_{i\in I} a_i } = 2b \)\\
|
|
|
\(\Rightarrow \sum\limits_{i\in I} a_i = b\)
|
|
|
|
|
|
\subsection{Bin Packing}
|
|
|
|
|
|
Gegeben: \( a_1,…,a_n,B,k\)\\
|
|
|
Gefragt: Kann man \(a_1,…,a_n\) auf k Bins der Größe B verteilen?
|
|
|
|
|
|
\bsp \(1,3,3,7,5,4\ ,B=5\)\\
|
|
|
\includegraphics{bilder/bin-packing.pdf}\\
|
|
|
\( \in NP\)
|
|
|
|
|
|
Partition $\le^P$ Bin Packing.\\
|
|
|
Sei \( a_1,…,a_n \) Eingabe für Partition.\\
|
|
|
Konstruiere Eingabe für Bin Packing:\\
|
|
|
\( a_1,…,a_n, B= \frac A2, k=2 \) mit \( A = \sum\limits_{i=1}^n a_i \)
|
|
|
|
|
|
\includegraphics{bilder/p-np.pdf}
|
|
|
|
|
|
\section{Approximationsalgorithmen}
|
|
|
|
|
|
\subsection{Bin Packing}
|
|
|
|
|
|
geg. $a_1,a_2,…,a_n$
|
|
|
|
|
|
\includegraphics{bilder/approx_bin.pdf}
|
|
|
|
|
|
|
|
|
\underline{1. Strategie}
|
|
|
|
|
|
\begin{itemize}
|
|
|
\item sortiere Eingabe aufsteigend zu \( a_1 \le a_2 \le .. \le a_n \)
|
|
|
\item fülle bin $i$ so weit wie möglich, für $i=1,2,...$ mit Gegenständen in sortierter Reihenfolge\\
|
|
|
\includegraphics{bilder/approx_bin_1.pdf}
|
|
|
\end{itemize}
|
|
|
|
|
|
\underline{2. Strategie}
|
|
|
|
|
|
\begin{itemize}
|
|
|
\item sortiere Eingabe absteigend zu \( a_1\ge a_2\ge ... \ge a_n \)
|
|
|
\item setze $a_i$ in den ersten bin, in den es noch hinein passt, für $i=1,…,n$.
|
|
|
\end{itemize}
|
|
|
|
|
|
\includegraphics{bilder/approx_bin_2.pdf}
|
|
|
|
|
|
|
|
|
\underline{Strategie 3: First Fit (FF)}
|
|
|
|
|
|
setze $a_i$ in den ersten bin, in den es noch hinein passt, für $i=1,2,…,n$
|
|
|
|
|
|
Betrachtung zu FF:\\
|
|
|
Sei $k^*$ die Anzahl der bins bei einer optimalen Lösung und $k$ die Anzahl der bins, die FF auf $a_1,...,a_n$ benützt.
|
|
|
|
|
|
Es gilt: $ \sum\limits_{i=1}^n a_i \le k^* $
|
|
|
|
|
|
Für FF gilt: alle bins, bis auf evtl. den letzten, haben Füllhöhe \(>\frac12\)
|
|
|
|
|
|
\includegraphics{bilder/approx_bin_3.pdf}
|
|
|
|
|
|
\( \Rightarrow 2 \sum\limits_{i=1}^n a_i > k \)\\
|
|
|
= \# bins, wenn alle genau $\frac12$ voll sind.
|
|
|
|
|
|
Folglich gilt:\\
|
|
|
\( k < 2 \sum\limits_{i=1}^n a_i \le 2k^* \)\\
|
|
|
\( \Rightarrow k < 2 k^* \)
|
|
|
|
|
|
Man kann sogar zeigen: $l\le \frac{17}{10} k^* $\\
|
|
|
Für FFD gilt sogar: $ k \le \frac{11}{9} k^* $
|
|
|
|
|
|
\subsection{Multi Processor Scheduling (MPS)}
|
|
|
|
|
|
geg. $m$ Prozessoren, $n$ Jobs\\
|
|
|
mit Laufzeiten $t_1,t_2,…,t_n$ und deadline D.
|
|
|
|
|
|
gefr. kann man die Jobs so auf die Prozessoren verteilen, dass alle Jobs in Zeit D fertig sind.
|
|
|
|
|
|
MPS ist NP-vollständig:\\
|
|
|
BinPacking $\le^P$ MPS\\
|
|
|
\( a_1,…,a_n,k,B \to t_i = a_i, i=1,…,n, m = k, D=B \)
|
|
|
|
|
|
\underline{Greedy-Strategie:}
|
|
|
|
|
|
\begin{itemize}
|
|
|
\item Ordne Job $i$ dem Prozessor zu, der aktuell die kleinste Ladung hat.
|
|
|
\end{itemize}
|
|
|
|
|
|
Sei $T$ die maximale Laufzeit bei der Greedy-Strategie und sei $T^*$ die Laufzeit bei der optimalen Lösung.\\
|
|
|
Für $T$ gilt:
|
|
|
\begin{enumerate}[1)]
|
|
|
\item $T^* \ge \frac1m \sum\limits_{i=1}^{n} t_i $
|
|
|
\item $T^* \ge \underset{i}{\text{max }} t_i$
|
|
|
\end{enumerate}
|
|
|
|
|
|
Für $T$ gilt:
|
|
|
\begin{addmargin}[1cm]{0cm}
|
|
|
Nach Ausführung von Greedy habe Prozess $i$ Ladung $T_i$.\\
|
|
|
Sei $i_0$ ein Prozessor mit $T_{i_0} = T$.\\
|
|
|
Sei Job $j$ der letzte Job, der Prozess $i_0$ zugewiesen wurde.\\
|
|
|
D.\,h. alle anderen Prozessoren haben zu diesem Zeitpunkt bereits eine größere Ladung. Es gilt also $T_i \ge T_{i_0} - t_j \forall i $\\
|
|
|
$\Rightarrow \underbrace{\sum\limits_{i=1}^n T_i}_{=\sum\limits_{i=1}^n ti} \ge m ( \underbrace{T_{i_0}}_{=T} - t_j ) $\\
|
|
|
$\Rightarrow \sum\limits_{i=1}^m T_i \ge m ( T-T_j)$\\
|
|
|
$\Rightarrow \frac1m \sum\limits_{i=1}^{m} t_i \ge T-t_j $\\
|
|
|
$\Rightarrow T \le \underbrace{\frac1m \sum\limits_{i=1}^{m} t_i}_{\le T^*} + \underbrace{t_j}_{\le T^*} $\\
|
|
|
$\Rightarrow$ \fbox{$T \le 2 T^*$}
|
|
|
\end{addmargin}
|
|
|
|
|
|
\bsp $t_i = 1, i=1,…,n-1$\\
|
|
|
$t_n = m$\\
|
|
|
\includegraphics{bilder/mps.pdf}\\
|
|
|
wähle $n = m (m-a) +1$\\
|
|
|
$T = 2m-1$\\
|
|
|
$T^* = m$
|
|
|
|
|
|
Greedy-Sortiert:
|
|
|
\begin{itemize}
|
|
|
\item sortiere Jobs, so dass\\
|
|
|
$t_1 \ge t_2 \ge … \ge t_n$
|
|
|
\item dann wie Greedy
|
|
|
\end{itemize}
|
|
|
\lemma $ 2t_{m+1} \le T^* $\\
|
|
|
\bew Betrachte Jobs $1,…,m+1$\\
|
|
|
Nach Schubfachschluss hat ein Prozessor $\ge 2$ Jobs (bei optimaler Lösung), d.\,h. Laufzeit $\ge \underbrace{t_i}_{\ge t_{m+1}} + \underbrace{t_j}_{\ge t_{m+1}}$
|
|
|
|
|
|
Gleiche Überlegung wie oben:\\
|
|
|
\begin{addmargin}[1cm]{0cm}
|
|
|
Prozessor $i_0$ mit maximaler Ladung $T$.\\
|
|
|
Prozessor $i_o$ habe $\ge2$ Jobs.\\
|
|
|
(Hätte Prozessor $i_0$ nur einen Job, dann ist $T=t_j=T^*$)\\
|
|
|
Es ist $j\ge m+1$, also $t_j \le t_{m+1}$, wobei Job $j$ wieder der letzte Job ist, der Prozessor $i_0$ zugewiesen wurde.
|
|
|
\end{addmargin}
|
|
|
|
|
|
Abschätzung von vorher:\\
|
|
|
$ T \le \underbrace{\frac1m \sum\limits_{i=1}^{n} t_i}_{\le T^*} + \underbrace{t_j}_{\le t_{m+1} \le \frac{T^*}{2}} $
|
|
|
|
|
|
\subsection{Vortex Cover}
|
|
|
|
|
|
% TODO VL vom 11.1.12 vervollständigen
|
|
|
\includegraphics{bilder/vertex_cover.pdf}
|
|
|
Greedy:
|
|
|
\begin{itemize}
|
|
|
\item wähle Knoten $v$ mit maximalem Grad
|
|
|
\item entferne $v$ (mit seinen Kanten)
|
|
|
\item wiederhole
|
|
|
\end{itemize}
|
|
|
|
|
|
\bsp\\
|
|
|
\includegraphics{bilder/vertex_cover_2.pdf}
|
|
|
\begin{align*}
|
|
|
deg(a_i) &= 1\\
|
|
|
deg(b_i) &= (n-2) +1 = n-1\\
|
|
|
deg(c_i) &= n
|
|
|
\end{align*}
|
|
|
Greedy wählt $c_1,c_2,…,c_{n-2}$, $a_1,a_2,…,a_n$, insgesamt als $2n-2$ Knoten.\\
|
|
|
Optimal wäre $b_1,…,b_n$ zu nehmen, also n Knoten.
|
|
|
|
|
|
\bsp\\
|
|
|
\includegraphics{bilder/vertex_cover_3.pdf}
|
|
|
\begin{align*}
|
|
|
N &= \sum\limits_{i=2}^{n} \lfloor \frac n i \rfloor\\
|
|
|
&\ge \sum\limits_{i=2}^{n} (\frac n i -1 )\\
|
|
|
&= \sum\limits_{i=2}^{n} \frac n i - (n-1)\\
|
|
|
&= n * \underbrace{ \sum\limits_{i=2}^{n} \frac1i}_{\ge \ln -1} -(n-1)
|
|
|
\end{align*}
|
|
|
|
|
|
$\big[$ Harmonische Reihe $\ln n \le \sum\limits_{i=1}^{n} \le \ln n +1 \big]$\\
|
|
|
$\Rightarrow N\ge n(\ln n-1) -n+1$\\
|
|
|
$= n \ln n - 2n+1$\\
|
|
|
greedy nimmt $c_N,c_{N-1},…,1$, $a_1,…,a_n$, also $N+n$ Knoten.\\
|
|
|
Verhältnis: $ \frac{N+n}{2} = \frac{n \ln n - n +1}{n} = \ln n -1 +\frac 1n $\\
|
|
|
D.\,h. die Strategie kann beliebig schlecht werden.
|
|
|
|
|
|
\includegraphics{bilder/vortex_cover_4.pdf}
|
|
|
|
|
|
\begin{enumerate}[1)]
|
|
|
\item $C\leftarrow \emptyset$
|
|
|
\item wähle beliebige Kante $(u,v)$
|
|
|
\item $C \leftarrow C \cup \{ u,v\}$
|
|
|
\item $G \leftarrow G - u,v$
|
|
|
\item wiederhole bis $G$ leer ist (2-4).
|
|
|
\end{enumerate}
|
|
|
|
|
|
Da eine vertex cover \underline{jede} Kante abdecken muss, ist auch in einer optimalen Lösung mindestens einer der beiden Endpunkte $u$ oder $v$ enthalten.
|
|
|
\[ \underbrace{|C|}_{\text{vc. vom Approx Alg.}} \le 2 \underbrace{|C^*|}_{\text{optimale Lösung}} \]
|
|
|
|
|
|
Besser: mit Approx Faktor $2-\frac{2}{\sqrt{u}}$ für eine Konstante $c$.
|
|
|
|
|
|
\subsection{Traveling Salesman Problem}
|
|
|
|
|
|
\subsubsection{Nearest Neighbor (NN)}
|
|
|
|
|
|
gehe immer zum nächstliegenden noch nicht besuchten Punkt.\\
|
|
|
\includegraphics{bilder/tsp_nn.pdf}
|
|
|
|
|
|
Metrik: $d$ erfüllt die Dreiecksungleichung\\
|
|
|
\includegraphics{bilder/tsp_dreieck.pdf}\\
|
|
|
$ d(x,y) \le d(x,z) + d(z,y) $
|
|
|
|
|
|
\includegraphics{bilder/tsp_nn_2.pdf}\\
|
|
|
Allgemein:
|
|
|
\begin{align*}
|
|
|
T &= \text{NN-Lösung}\\
|
|
|
T^* &= \text{optimale Lösung}\\
|
|
|
|T| &\le \log_n |T|^*
|
|
|
\end{align*}
|
|
|
(TSP mit $\triangle$-Ungleichung)
|
|
|
|
|
|
\subsubsection{Nearest Insertion}
|
|
|
|
|
|
bilde Kreis und füge Knoten ein
|
|
|
\begin{itemize}
|
|
|
\item Start mit 3 (beliebigen) Knoten und verbinde zu Dreieck.
|
|
|
\item wähle Knoten $v$ der noch nicht Besucht ist und füge $v$ in den Kreis ein.
|
|
|
\end{itemize}
|
|
|
|
|
|
Auswahl von $v$:\\
|
|
|
\includegraphics{bilder/tsp_nn.pdf}
|
|
|
|
|
|
wähle $v$ mit minimalem Abstand zum Kreis:
|
|
|
\[ d(c,v) = min d(u,v) \quad u \in V\]
|
|
|
füge $v$ so ein, dass sich der Kreis möglichst wenig verlängert. D.\,h. wähle Nachbar $w$ von $v$ so, dass
|
|
|
\[ Cost(v) = d(u,v) + d(v,w) - d(u,w) \]
|
|
|
minimal ist.
|
|
|
|
|
|
Noch $\triangle$-Ungleichung ist
|
|
|
\begin{align*}
|
|
|
d(v,w) \le d(u,v) + d(u,w)\\
|
|
|
\Rightarrow d(v,w) - d(u,w) \le d(u,v)\\
|
|
|
\Rightarrow cost(v) \le 2*d(u,v)
|
|
|
\end{align*}
|
|
|
|
|
|
\begin{itemize}
|
|
|
\item Wiederhole Insertion-Schritt bis alle Knoten im Kreis sind.
|
|
|
\end{itemize}
|
|
|
|
|
|
\beh Sei $C$ der Kreis der durch NI berechnet wird und $C^*$ eine optimale TSP-Tour.\\
|
|
|
Dann ist $d(C) \le 2 * d(C^*) $\\
|
|
|
$ d(C) = \sum\limits_{(u,v) \in C} d(u,v) $
|
|
|
|
|
|
\bew Vergleich mit der Berechnung aufspannender Bäume, wähle jeweils Knoten $v$ der am nächsten zum aktuellen Baum liegt.\\
|
|
|
NI wählt ebenfalls diesen Knoten $v$ aus.\\
|
|
|
\includegraphics{bilder/tsp_ni_bew.pdf}
|
|
|
|
|
|
Aufspannender Baum T vergrößert sich um $d(u,v)$, Kreis vergrößert sich um $cost(v) \le d(u,v)$.\\
|
|
|
\( \Rightarrow \) am ende gilt: $ d(c) \le 2 * d(T) $
|
|
|
|
|
|
Sei $C^*$ Kreis minimaler Länge ( = opt. TSP-Tour ).\\
|
|
|
\includegraphics{bilder/tsp_ni_bew2.pdf}\\
|
|
|
Lasse irgendeine Kante weg. Dann entsteht ein Baum $T'$, ein aufspannender Baum. Folglich ist $d(T) \le d(T')$, da $T$ minimal ist.\\
|
|
|
Außerdem ist $d(T') < d(C^*)$\\
|
|
|
$\Rightarrow d(T) \le d(C^*)$\\
|
|
|
$\Rightarrow d(C) \le 2 * d(T) \le 2*d(C^*)$\\
|
|
|
$\Rightarrow $ \fbox{$d(C) \le 2*d(C^*)$} $\Box$
|
|
|
|
|
|
Varianten:
|
|
|
\begin{itemize}
|
|
|
\item Farthest Insertion (FI)
|
|
|
\item Random Insertion (RI)
|
|
|
\end{itemize}
|
|
|
|
|
|
\subsubsection{Christofides}
|
|
|
|
|
|
\begin{enumerate}[1)]
|
|
|
\item Konstruiere minimal aufspannenden Baum $T$.\\
|
|
|
Dann ist $d(T) \le d(C^*)$\\
|
|
|
\includegraphics{bilder/tsp_christofides.pdf}
|
|
|
\item verdopple alle Kanten
|
|
|
\item Konstruiere Euler-Tour $E$ (mittels DFS)\\
|
|
|
$D(E) = 2*d(T) $
|
|
|
\item Konstruiere daraus TSP-Tour durch Abkürzungen\\
|
|
|
\includegraphics{bilder/tsp_christofides_2.pdf}
|
|
|
\end{enumerate}
|
|
|
|
|
|
\underline{Verbesserung}
|
|
|
|
|
|
\includegraphics{bilder/tsp_christofides_adv.pdf}\\
|
|
|
Erweitere T um Kanten, so das jeder Knoten geraden Grad hat.
|
|
|
|
|
|
Betrachte $U=$ Knoten mit ungeradem Grad in $T$
|
|
|
|
|
|
\lemma $|u|$ ist gerade\\
|
|
|
\bew $ \sum\limits_{v\in V} grad(v) = 2m $ ($m$ = Anzahl Kanten), da in der Summe jede Kante zweimal gezählt wird.\\
|
|
|
\(\Rightarrow \underbrace{2m}_{\text{gerade}} = \sum\limits_{u\in U} grad(u) + \underbrace{\sum\limits_{v \in V-U} grad(v)}_{\text{gerade}} \)\\
|
|
|
\(\Rightarrow \sum\limits_{u\in U} grad(u) \) ist gerade\\
|
|
|
\(\Rightarrow |n|\) gerade
|
|
|
|
|
|
Verbinde Knoten in $U$ paarweise, so dass die Summe der hinzugefügten Kanten möglichst klein ist.
|
|
|
|
|
|
Matching auf $U$.\\
|
|
|
\begin{wrapfigure}{l}{2cm}
|
|
|
\includegraphics{bilder/tsp_christofides_adv_matching.pdf}
|
|
|
\end{wrapfigure}
|
|
|
Perfect Matching $M$ ist eine Menge von Kanten, so dass jeder Knoten zu genau einer Kante aus $M$ gehört.\\
|
|
|
Es gibt effiziente Verfahren zu Berechnung von minimalem perfect Matching.
|
|
|
|
|
|
Dann weiter wie vorher: konstruiere Eulertour $E$ und daraus TSP-Tour $C$.\\
|
|
|
Es gilt: $d(E) = d(T) + d(M) \ge d(C)$
|
|
|
|
|
|
\includegraphics{bilder/tsp_christofides_adv_kreis.pdf}
|
|
|
|
|
|
Nehme jede zweite Kante\\
|
|
|
\(\Rightarrow\) perfect Matching $M_1$\\
|
|
|
Rest ist ebenfalls perfect Matching $M_2$
|
|
|
\begin{align*}
|
|
|
\Rightarrow d(C^*) &= d(M_1) + d(M_2)\\
|
|
|
&\ge d(M) + d(M)\\
|
|
|
&= 2 * d(M)\\
|
|
|
\Rightarrow d(M) &= \frac12 * d(C^*)\\
|
|
|
\Rightarrow d(C) &\le d(T) + d(M)\\
|
|
|
&\le d(C^*) + \frac * d(C^*)\\
|
|
|
&= \frac32 d(C^*)
|
|
|
\end{align*}
|
|
|
|
|
|
\(\triangle\)TSP\\
|
|
|
TSP ohne $\triangle$-Ungleichung:\\
|
|
|
\includegraphics{bilder/tsp_dreieck_2.pdf}\\
|
|
|
\satz Sei $ c > o $ beliebig.\\
|
|
|
$P \ne NP \Rightarrow $ es gibt keine $c$-Approximation für TSP.
|
|
|
|
|
|
\bew Betrachte folgende Reduktion von $HAM \le^P TSP$.\\
|
|
|
Sei $G = (V,E)$ ein Graph mit $|V| = n$.\\
|
|
|
Konstruiere Eingabe für TSP mit $n$ Städte und Abständen $d$:\\
|
|
|
\[ d(i,j) = \begin{cases}1,& \text{falls } (i,j) \in E \\ c * n, & \text{sonst} \end{cases} \]
|
|
|
\includegraphics{bilder/tsp_graph.pdf}
|
|
|
|
|
|
Dann gilt:
|
|
|
\begin{enumerate}
|
|
|
\item $G \in HAM \Rightarrow L^* = $ optimale Länge einer Rundreise $ = n$
|
|
|
\item $G \not\in HAM \Rightarrow L^* \ge n-1 + c* n > c * n$
|
|
|
\end{enumerate}
|
|
|
|
|
|
Zeige: Wenn es einen Algorithmus $A$ gibt, eine $c$-Approximation an TSP, dann ist $HAM \in P$ und folglich ist dann $P = NP$.
|
|
|
|
|
|
$A$ ist $c$-Approximation, d.\,h. sei L die Länge der TSP-Tour, die $A(n,d)$ berechnet, dann gilt: $L\le c * L^* $
|
|
|
|
|
|
Sei $G=(V,E)$ Eingabe für $HAM$. Reduziere $G$ wie oben zu $(n,d)$. Sei $L =$ Länge von $ A(n,d)$.
|
|
|
|
|
|
Dann gilt:
|
|
|
\begin{enumerate}
|
|
|
\item $G\in HAM \Rightarrow L^* = n \Rightarrow L \le c * n $
|
|
|
\item $G\not\in HAM \Rightarrow L^* > c*n \Rightarrow L > c * n $
|
|
|
\end{enumerate}
|
|
|
|
|
|
D.\,h. $G \in HAM \Leftrightarrow L \le c*n$\\
|
|
|
$\Rightarrow HAM \in P$
|
|
|
|
|
|
\bsp Vertex Cover\\
|
|
|
$P\ne NP \Rightarrow $ es gibt keine $c$-Approximation für $c<\frac{16}{15}$
|
|
|
|
|
|
\subsection{Subset Sum}
|
|
|
|
|
|
Für Subset Sum git es eine Approximation, die auf Eingabe $(a_1,…,a_n,b,\epsilon), \epsilon > 0$ eine $(1+\epsilon)$-Approximation liefert.\\
|
|
|
\includegraphics{bilder/subset_sum_opt.pdf}
|
|
|
|
|
|
Optimierungsversion: $I\le \{ 1,…,n\}$ sodass $ \sum\limits_{i\in I} a_i$ maximal und $\le b$
|
|
|
|
|
|
\section{PSPACE}
|
|
|
|
|
|
$P \subseteq NP \subseteq \underline{\underline{PSPACE}} \le EXP$\\
|
|
|
|
|
|
\subsection{True Quantified Boolean Formular (TQBF)}
|
|
|
|
|
|
$ \forall x \exists y (x \land \exists z (y \land z))$
|
|
|
|
|
|
Voll quantifizierte Formeln sind wahr oder falsch.
|
|
|
|
|
|
$F(x_1,…,x_n) \in SAT $\\
|
|
|
$\Leftrightarrow \exists x_1 \exists x_2 … \exists x_n F(x_1,…,x_n) \in TQBF$
|
|
|
|
|
|
$TQBF \in PSPACE$
|
|
|
|
|
|
\includegraphics{bilder/pspace_tqbf.pdf}
|
|
|
|
|
|
Stelle Formel als Schaltkreis dar und werte mittels Tiefensuche aus. Es gilt: $TQBF$ ist $PSPACE$-vollständig.\\
|
|
|
Jede $QBF$-Formel lässt sich äquivalent umschreiben in $Q_1x_1Q_2x_2…Q_nx_n F(x_1,…,x_n)$ mit $Q_1 = \exists, Q_2 = \forall, …$ alternierend und $F$ in $3-KNF$ ist. (quantorenfrei)
|
|
|
|
|
|
\underline{Geographie}
|
|
|
|
|
|
Gegeben: Graph $G$, gerichtet.\\
|
|
|
Knoten $S$ (Startknoten).\\
|
|
|
Zwei Spieler ziehen Abwechselnd.\\
|
|
|
Spieler I started in $S$ und zieht zu einem Nachbar von $S$. Dann zieht Spieler II, …\\
|
|
|
Dann immer abwechselnd.\\
|
|
|
Kein Knoten darf mehrfach besucht werden. Es verliert der Spieler, der nicht mehr Ziehen kann.\\
|
|
|
$\textsc{Geo} = \{ (G,s) \mid $ es gibt eine Gewinnstrategie für Spieler I $\}$
|
|
|
|
|
|
$ TQBF \le^P \textsc{Geo}: F = \exists x_1 \forall x_2 … Q_nx_n (C_1 \land C_2 \land … \land C_m)$
|
|
|
|
|
|
Konstruiere $G,s$:
|
|
|
|
|
|
\includegraphics{bilder/tqbf_geo.pdf}
|
|
|
|
|
|
\textsc{Geo} ist $PSPACE$-Vollständig
|
|
|
|
|
|
Ebenso:
|
|
|
\begin{itemize}
|
|
|
\item $NFA$-Äquivalenz
|
|
|
\item Reguläre Ausdrücke-Äquivalenz
|
|
|
\end{itemize}
|
|
|
|
|
|
$P\subseteq NP \subseteq PSPACE \subseteq EXP$\\
|
|
|
Es ist $P \ne EXP$
|
|
|
|
|
|
\end{document}
|
