\documentclass[12pt, twoside, a4paper]{article}
\setlength\topmargin{0in}
%\setlength\headheight{0in}
%\setlength\headsep{0in}
\setlength\textheight{9in}
\setlength\textwidth{6in}
%\setlength\oddsidemargin{0.26in}
\setlength\oddsidemargin{0in}
\setlength\evensidemargin{0cm}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{ngerman}
\usepackage{amsmath,amssymb,stmaryrd}
\usepackage{calc}
\usepackage[thmmarks,noconfig]{ntheorem}
\usepackage{graphicx}
\include{definitionen08}
%\renewcommand{\P}{{\Pol}}
\newcommand{\true}{\ensuremath{\operatorname{true}}}
\newcommand{\false}{\ensuremath{\operatorname{false}}}

\usepackage{rotating}

\pagestyle{empty}
\begin{document}

\title{Komplexitätstheorie (Martin Hofmann)}
\author{Mitgeschrieben von Bernhard Weiß, Sebastian Goebl und anderen}
\date{Mitschrift aus dem WiSe 2008/09}

\maketitle
\tableofcontents
\newpage
\pagestyle{headings}
%%%%%%%%%%
\pagenumbering{Roman}
\setcounter{tocdepth}{2}

\tableofcontents%[current, hidesubsections] 
\newpage
%%%%%%%%%%%
\pagenumbering{arabic} 



\section{Turingmaschinen, Berechenbarkeit, Komplexitätsklassen}

\subsection{Turingmaschinen}
%\subsection{Definition (k-Band Turingmaschine)}

\begin{definition}(k-Band Turingmaschine)
 Eine k-Band Turingmaschine ist ein Quintupel
 $T = \langle Q, \Simga, I, q_0, F \rangle$ wobei
 \begin{itemize}
 \item
 Q ist endliche Menge von Zuständen
 \item
 $\Simga$ ist eine endliche Menge von Symbolen
 \item
 I ist eine Menge von Quintupeln der Form $(q, s , s',d,q')$ wobei $q,q' \in Q, s, s' \in \Sigma^k, d \in \{L,R,s\}^k$. 
 F"ur alle $q,s$ existiert höchstens ein Quintupel der Form $(q,s,-,-,-)$ in der Menge I
 \item
 $q_0 \in Q$ Anfangszustand
 \item
 $F \subset Q$ Endzustände
 
 \end{itemize}
\end{definition}
%%%%%%%%%%%%%%%%%%%
\begin{Beispiel}%%%
%% Begin Beispiel%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%
 $\Simga = \{ 0, 1,\square,\# \}, k = 2, Q = \{q_0, q_1, q_2, q_3, q_4\}$
 \begin{enumerate}
\item 
$q_0, (\square, \square), (\#,\#), (S,S), q_1$
\item
$q_0, (1, \square), (1, \#), (S,S), q_2$
\item
$q_0, (0, \square), (0,0) (R,R), q_3$
\item
$q_3, (0, \square), (0,1) (R,R), q_3$
\item
$q_3, (\square, \square), (\#,\#), (S,S), q_2$
\item
$q_3, (1, \square), (1, \square), (R,L) , q_4$
\item
$q_4, (1,1), (1,1) (R,L), q_4$
\item
$q_4, (\square, 0), (\square, 0), (S,S), q_1$
\item
$q_4, (1,0), (1,0), (S,S), q_2$
\item
$q_4, (\square, 1), (\square, 1), (S,S), q_2$
\end{enumerate}

 

%%%%%%%%%%%%%%%%%
\end{Beispiel}
\begin{definition}[Definition (Globaler Zustand, Konfiguration)]
 Sei $T = (Q, \Sigma, I, q_0, F)$ eine k-Band Turingmaschine. 
 Ein Globaler Zustand (synonym Konfiguration) von T ist ein Tripel $\Scal = (q, w, w')$
 wobei $q \in Q, w \in (\Sigma^\ast)^k, w' \in (\Sigma^+)^k$
 (q ist der aktuelle Zustand, w das Wort vor dem Schreib/Lesekopf und w' das Wort auf und nach dem Schreib/Lesekopf). 
 Seien $\Scal, \Scal'$ Konfigurationen. Man schreibt $\Scal \toweil T \Scal'$ gesprochen $\Scal'$ ist die Folgekonfiguration von $\Scal$ wenn gilt:
 $\Scal = (q, w, w'), q \notin F$
 \begin{itemize}
\item
Sei $w = ( w_1, \ldots w_k), w' = (w_1', \ldots w_k'), a_i = $ erstes Symbol von $w_i'$

Sei $(q, (a_1,\ldots, a_k), (b_1, \ldots b_k) (d_1, \ldots d_k), q') \in I$
Dann $\Scal' = (q', v,v')$
$v = (v_1, \ldots, v_k), v' = (v_1', \ldots, v_k')$
wobei
$v_i = \begin{cases} 
w_i & d_i = S\\
u  & d_i = L, w_i = uc\\
\epsilon  & d_i = L, w_i = \epsilon\\
w_i b_i & d_i = R
 \end{cases}$
 $w_i' = a_i u, a_i \in \Sigma, u \in \Sigma^\ast$
 $v_i' = \begin{cases} 
b_i u & d_i = S\\
c b_i u & d_i = L, c = \text{Letztes Symbol von } w_i\text{ bzw }\square\text{ falls }w_i = \epsilon\\
u & d_i = R
 \end{cases}$

 \end{itemize}
\end{definition}
\begin{Definition}[Start-Konfiguration]
 Sei $X \in \Sigma^\ast$ und $\square$ kommt nicht in x vor.
 Die Startkonfiguratin für T auf eingabe x ist definiert definiert als
 $(q_0, (\epsilon, \ldots, \epsilon), (x, \square, \ldots \square)$
\end{Definition}
\begin{Definition}[Berechnung]
 Berechnung von T auf Eingabe x ist eine endliche oder unendliche Folge von Konfigurationen, $\Scal_0, \ldots \Scal_n$ bzw $\Scal_0, \Scal_1, \ldots$, sodass
 \begin{itemize}
 \item
 $\Scal_0$ ist die Startkonfiguration von T für x
 \item
 $\Scal_i \toweil T \Scal_{i+1}$
 \item
 Falls die Folge endlich ist mit letztem Element $\Scal_n$ so existiert keine Folgekonfiguration $\Scal'$ mit $\Scal_n \toweil T \Scal'$
 \end{itemize}
\end{Definition}

\begin{Definition}[Akzeptormaschine]
Eine Akzeptormaschine ist eine TM T mit
$F = \{q_A, q_R\}$(akzeptierender und verwervender Zustand)
eine Eingabe x wird von solche einer Maschine akzeptiert, falls die Berechnung von x aus endlich ist und im Zustand $q_A$ endet
\end{Definition}
\begin{bemerkung}
Die Beispielmaschine von oben akzeptiert alle Eingaben der Form $0^n1^n$.
\end{bemerkung}
\begin{definition}[Erkannte Sprache]
 Sei T eine Turingmaschine
 $L(T) := \{x | \underbrace{T(x)}_{\text{Berechnung von T mit Startkonfiguaration x}}$ hält in Zustand $g_A\}$. 

 L heißt akzeptierbar, wenn $L= L(T)$ für eine Maschine T
\end{definition}
\begin{bemerkung}
akzeptierbar = semi-entscheidbar = rekursiv entscheidbar
\end{bemerkung}
\begin{Definition}
 L wird von TM T entschieden, wenn gilt:
 $x \in L \To T(x)$ hällt in Zustand $g_A$
 $x \notin L \To T(x)$ hält in Zustand $g_R$
 
L heißt entscheidbar, wenn $\exists T$, sodass L wird von T entschieden
\end{Definition}
\begin{bemerkung}
Wenn keine Verwechslungsgefahr besteht, verwenden wir die Notation $L(T)$ auch f"ur die von $T$ entschiedene Sprache. 
\end{bemerkung}
\begin{bemerkung}
Es gibt Sprachen L, die akzeptierbar, aber nicht entscheidbar sind.
\end{bemerkung}
\begin{bemerkung}
Meist betrachtet man eine Teilmenge $\Sigma_{in} \subseteq \Sigma$ als Alphabet und erweitert Akzeptierbarkeit und Entscheidbarkeit auf Sprachen $L \subseteq \Sigma_{in}^\ast$.
Manche Autoren definieren Turingmaschinen als Tupel $(\Sigma, \Sigma_{in}, Q, I, q_0, F)$
\end{bemerkung} 
\subsection{Zeitkomplexit"at, Speedup und Hierarchiesatz}
\begin{Definition}[Zeitkomplexität]
 Sei T eine Turingmaschine $x \in \Simga^\ast$
 $\TIME_T(x) = $Länge der Berechnung $T(x)$, undefiniert falls $T(x)$ nicht hält.
\end{Definition}
\begin{bemerkung}
$\TIME_T: \Sigma^\ast \to \N$ ist partielle Funktion

$|x| := $ Länge von x
\end{bemerkung}
\begin{Satz}[Speeduptheorem]
Sei T ein TM, die L entscheidet und $d \in \N$
Dann existiert TM $T'$ die auch L entscheidet und außerdem erfüllt:
$\TIME_{T'}(x) = \frac 1 d \TIME_T(x) + |x| + 1 $
%%%%%%%%%%%%%%%%%%%
\end{Satz}
\begin{beweis}[Idee]
%% Begin Beweis%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%
 $T'$ verwendet als Alphabet
 $\Sigma' := \Sigma^d$
 Berechne alle Übergänge von einem Block zum nächsten im voraus und speichere sie in der (riesigen!) Zustandstafel I' von T' ab.
\end{beweis}
%%%%%%%%%%%%%%%%% 
\paragraph{Ziel:}
Definition von $\TIME(f)$ wobei f eine Funktion $\N \to \N$, z.B.\ $ f(n) = n^e$

\begin{Definition}[Zeitkonstruierbar]
 Eine Funktion $f: \N \to \N$ heißt zeitkonstruierbar, wenn eine TM T existiert, die bei Eingabe x hält nach $\leq c \cdot f(|x|)$ Schritten für ein festes $c \in \N$ und auf einem Band die Ausgabe $1^{f(|x|)}$ liefert
 ( $ \square \square \square \underbrace{ 1 1 \ldots 1 1}_{ f(|x|) \text{ Stück}} \square \square$)
\end{Definition}

\begin{Satz}
$f(n) = n, f(n) = n \log n$ sind zeitkonstruierbar.
Falls f,g zeitkonstruierbar, $k \in \N$ dann auch:
$k \cdot f, f+ k, f+g, f\cdot g, f^g, f!, f \circ g$. 
Zu jeder berechenbaren Funktion $f$ existiert eine zeitkonstruierbare Funktion $r$, sodass $f(n)\leq r(n)$. 
\end{Satz}
\begin{Definition}
 Sei f zeitkonstruierbar.
 $\TIME (f)$ ist definiert als die Menge aller Sprachen L für die eine TM T existiert  mit
 $\TIME_T(n) \leq x \cdot f(|x|)$ für ein $c \in \N$ 
\end{Definition}
Man schreibt $\TIME(f(n))$ statt $\TIME(f)$ und auch $\TIME(n^2)$ statt $\TIME(sq)$ wobei $sq(n) = n^2$

\begin{Beispiel}
 $\{ 0^n 1^n | n \geq 0 \} \in \TIME(n)$
 'Kürzeste Wege' $\in \TIME(n^2)$
 'Sudoku lösen' $\in \TIME(2^n)$
 $\{0^n 1^n | n \geq 0 \} \in \TIME(2^n)$
 ADDITION $\in \TIME(n)$
 MULTIPLIKATION $\in \TIME(n^2)$
\end{Beispiel}
\begin{Definition}
 $P := \bigcup_{k \geq 1} \TIME(n^k)$

 $\EXP := \bigcup_{k \geq 1} \TIME(2^{n^k})$

 $E := \bigcup_{k \geq 1} \TIME(2^{kn})$

 ACHTUNG:
 $2^{5n} \notin O(2^n)$ d.h.
 für keine Konstante c gilt:
 $2^{5n} < c 2^n$
\end{Definition}
\begin{Satz}[Zeithierarchiesatz]
Sei f zeitkonstruierbare Fkt.
Dann gilt: $\TIME(f(n)) \subsetneq \TIME(n^2 f(n)^2)$
%%%%%%%%%%%%%%%%%%%
\begin{Beweis}%%%
%% Begin Beweis%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%
 Betrachte folgenden Algorithmus:
 \begin{itemize}
 \item[]
 Eingabe: TM T /* codiert als 01 Folge /*
 \item[1]
 Berechne $N := f(|T|) + |T| + 1$
 \item[2]
 Simuliere T(M) für N Schritte.
 \item[3]Ausgabe:
 Falls diese Berechnung akzeptiert:
 REJECT
 sonst:  ACCEPT
 \end{itemize}
 Setze 
\[
L_f = \{T \mid  T(T) \text{ akzeptiert \emph{nicht} nach }f(|T|) +|T| +1\text{ Schritten}
\}
\]
 Klar: Der angegebene Algorithmus ist ein Entscheidungsverfahren für $L_f$.

 Sei $T_f$ eine Turingmaschine, die diesen Algorithmus implementiert und insbesondere $L_f$ entscheidet.
 Wir zeigen zunächst, dass $L_f \notin \TIME(f(n))$. 

 Falls doch, so sei $T_0$ eine Turingmaschine die $L_f$ entscheidet und außerdem $\TIME_{T_0} (x) \leq c f(|x|)$.
 Nach Speedup Theorem können wir oBdA annehmen dass $\TIME_{T_0} (x) \leq f(|x|) + |x| + 1$.
 Es gibt zwei Fälle:
 entweder $T_0 \in L_f$ oder $T_0 \notin L_f$.
 Falls $T_0 \in L_f$ dann müsste $T_0 (T_0)$ nach $\leq f(|T_0|) + |T| + 1$ Schritten verwerfen (also insbesondere überhaupt verwerfen). Dann aber wäre $T_0 \notin L_f$ , weil $T_0$ die Sprache $L_f$ entscheidet
 Falls $T_0 \notin L_f$ dann müsste $T_0$ die Eingabe verwerfen, und aufgrund der Annahme an $\TIME_{T_0}$ müsste dies nach spätestens $f(|T_0|) + |T_0| +1$ Schritten geschehen, also wäre $T_0 \in L_f$.
 
\medskip 

 Komplexitätsabschätzung des Algoritmus von oben:
1: $c f(|T|)$ Schritte (weil f zeitkonstruierbar)
2: Man muss die k Bänder der eingegeben Maschine T auf einem Band speichern (durch Hintereinanderschreiben), da man nicht inputabhängig neue Bänder anfordern kann.
Außerdem muss das Alphabet der Maschine T mit festem Alphabet codiert werden, da man nicht inputabhängig neue Arbeitssymbole anfordern kann. Ein Arbeitsband von T                                                                   
enthält hoechstens $f(|T|) + |T| + 1$ Symbole. Da $f$                                                                                          
zeitkonstruierbar ist, gilt $f(n)\geq n$, also $f(|T|)+|T|+1  = O(f(|T|)$. 
Die Kodierung einer globalen Konfiguration erfordert somit $O(|T|^2 \cdot f(|T|))$ Symbole, wenn man beachtet, dass sowohl die Zahl der Bänder von T, als auch die Alphabetgröße von $T$ durch $|T|$ beschränkt sind.                                                                                  
                                                            
Um einen Schritt zu simulieren, muss man auf dieser langen Codierung hin- und her navigieren, sodass sich ein Aufwand von $O(|T|^2 \cdot f(|T|))$ ergibt. Da nun $f(|T|)+|T|+1$ Schritte zu simulieren sind, kann der Gesamtaufwand durch                                                                  
$O(|T|^2 \cdot f(|T|)^2)$ beschränkt werden. 
%%%%%%%%%%%%%%%%%
\end{Beweis}
\begin{Korollar} $P \subsetneq \EXP$\end{Korollar}
\begin{beweis}
$\Pol \subseteq \TIME(2^n)$ weil $2^n$ schneller wächst als jedes Polynom.\\
$\TIME(2^n) \subsetneq \TIME(n^2 \cdot (2^n)^2)$ wegen Zeithierarchiesatz.\\
$\TIME(n^2 \cdot (2^n)^2) \subseteq \EXP$
\end{beweis}
\begin{Satz}[{GAP-Theorem}]
Es existiert eine berechenbare Funktion $f: \N \to \N$ T', sodass $\TIME (f(n)) = \TIME(2^{f(n)})$.
Allerdings ist f nicht zeitkonstruierbar.
\end{Satz}
\subsection{Nichtdeterminismus, wichtige Komplexitätsklassen und deren Beziehungen}
\begin{Definition}[Nichtdeterministische Turingmaschine]
Wie deterministische Turingmaschine aber $I$ beliebig
$(I \subseteq Q \times \Sigma \times \Sigma \times Q \times \lbrace S, L, R \rbrace )$
Zu gegebenem $q$, $a$ kann es mehrere Quintupel in $I$ der Form $(q, a, -, -, -)$ geben.
Zu einer Eingabe $x \in \Sigma^*$ definiert man den Berechnungsbaum wie folgt:
\begin{itemize}
	\item Der Binärbaum ist endlich verzweigt aber möglicherweise unendlich.
	\item Die Wurzel ist mit der Startkonfiguration von $T$ auf $x$ beschriftet.
	\item Ist ein Knoten mit Konfiguration $S$ beschriftet und sind $S_1, ..., S_n $ die Nachfolgekonfigurationen von $S$, so hat der Knoten $n$ Kinder
	die mit diesen beschriftet werden.
\end{itemize}
\end{Definition}
\begin{Definition}
Eine nichtdeterministische Turingmaschine $T$ akzeptiert ein Wort $x \in \Sigma^*$ wenn es im Berechnungsbaum von $T$ auf $x$ einen Ast gibt,
der mit einer akzeptierenden Endkonfiguration endet und außerdem alle Äste endlich sind.
Ein Wort $x$ wird verworfen, wenn es nicht akzeptiert wird, d.h. es gibt einen unendlichen Ast oder alle Äste enden in einer verwerfenden Konfiguration.
\end{Definition}
\begin{Bemerkung}
Alle Nichtdeterministischen Turingmaschinen die wir betrachten, haben endl. Berechnungsbäume.
\end{Bemerkung}
\begin{Definition}[$\NTIME$]
Sei $T$ Nichtdeterministische Turingmaschine $x \in \Sigma^*$

$\NTIME_T(x)=
\begin{cases}
\text{Länge des kürzesten akzeptierenden Astes, falls existent}\\
\text{Länge des kürzesten Astes überhaupt, sonst}
\end{cases}$
\end{Definition}
\begin{Bemerkung}
Meist sind Nichtdeterministische Turingmaschinen so gebaut, dass alle Äste gleich lang sind.
\end{Bemerkung}
\begin{Definition}[$\NTIME(f(n))$]
Sei $f$ zeitkonstruierbar.
$\NTIME(f(n))= \lbrace L \mid $ es existiert Nichtdeterministische Turingmaschine $T$, $c>0: \forall x$. $x \in L \Leftrightarrow T$ akzeptiert
$x$ und $\NTIME_T(x) \leq c \cdot f(|x|) \rbrace $
\end{Definition}
\begin{Definition}[$\Pol$, $\NP$, $\E$, $\EXP$, $\NEXP$, $\NE$]
$\Pol= \bigcup_{k \geq 0} \TIME(n^k)$ /* polynomielle Laufzeit */

$\NP = \bigcup_{k \geq 0} \NTIME(n^k)$ /* nichtdeterministisch, polynomielle Laufzeit */

$\E = \bigcup_{k \geq 0} \TIME(2^{kn})$

$\NE = \bigcup_{k \geq 0} \NTIME(2^{kn})$

$\EXP = \bigcup_{k \geq 0} \TIME(2^{n^k})$

$\NEXP = \bigcup_{k \geq 0} \NTIME(2^{n^k})$
\end{Definition}
\begin{Bemerkung}
$\Pol=$'praktisch berechenbar'?
Lässt sich ein Graph $G$ knotenfrei im $\R^3$ zeichnen? Dieses Problem ist in $\Pol$ aber kein Algorithmus konnte bisher konkret angegeben werden.
\end{Bemerkung}
\begin{Satz}[Bekannte Beziehungen]

\begin{tabular}[t]{ccc}
$\Pol$ & $\subseteq^\dagger$ & $\NP$\\
\begin{turn}{-90} $\subsetneq^*$ \end{turn} & & \begin{turn}{-90} $\subsetneq^*$ \end{turn}\\
$\E$ & $\subseteq^\dagger$ & $\NE$\\
\begin{turn}{-90} $\subsetneq^*$ \end{turn} & & \begin{turn}{-90} $\subsetneq^*$ \end{turn}\\
$\EXP$ & $\subseteq^\dagger$ & $\NEXP$\\
\end{tabular}\\
*folgt aus Zeithierarchiesätzen\\
$\dagger$ Die Echtheit dieser Inklusionsbeziehungen wird vermutet, konnte aber nicht gezeigt werden.
\end{Satz}
\begin{Satz}
$\NP\subseteq \EXP$
\end{Satz}
\begin{beweis}
Durch systematische Exploration aller Pfade im Berechnungsbaum.
\end{beweis}
\begin{Satz}
$\Pol=\NP \Rightarrow \E=\NE$ (also $\E \neq \NE \Rightarrow \Pol \neq \NP)$\\
\end{Satz}
\begin{beweis}[durch padding]
Sei $\Pol=\NP$ und $L \in \NE$\\
Definiere $L^*$ über $\Sigma \uplus \lbrace \# \rbrace$\\
$L^* = \lbrace w\underbrace{\#...\#}_{2^{|w|}-|w|} \mid w \in L \rbrace $\\
Wir behaupten: $L^*$ ist in NP:\\
Eingabe: $w'$\\
Prüfe ob $w'=w\underbrace{\#...\#}_{2^{|w|}-|w|}$\\
Prüfe ob $w \in L$ /* $w$ aus Zerlegung von $w'$ */ mit gegebenem nichtdeterministischem Algorithmus.\\
Zeitbedarf dieses Algorithmus:\\
$O(|w'|)$ für Zerlegung\\
NB: $|w| = O(\log |w'|)$\\
Zeitbedarf für Test ob $w \in L$\\
$O(2^{k \cdot |w|}) = O(2^{k \cdot O(\log(w'))}) = O(|w'|^{k \cdot O(1)})$ /* polynomiell */\\
also Gesamtlaufzeit des (nichtdeterministischen!) Algorithmus: $O(|w'|^{O(1)})$ also in $\NP$.\\

Nach Annahme gibt es ein polynomielles deterministisches Verfahren für $L^*$. Wir konstruieren
daraus ein Verfahren ''in $\E$'' wie folgt:\\

EINGABE $w \in \Sigma^*$\\
Konstruiere $w'=w\#...\#$\\
Prüfe mit deterministisch polynomiellem Verfahren ob $w' \in L^*$\\
Falls ja: Akzeptiere\\
sonst: Verwirf\\

Laufzeit dieses Verfahrens:
\begin{itemize}
	\item Konstruktion von $w'$: $O(2^{O(|w|)})$
	\item Test ob $w' \in L^*$:\\
		\quad $O(|w'|^k)$ \quad $k$ fest\\
		$= O((2^{|w|})^k) = O((2^{k \cdot |w|}))$
\end{itemize}

$\leadsto$ Algorithmus läuft in Zeit $O(2^{O(|w|)})$ also $L \in E$ wzbw.
\end{beweis}
\begin{Korollar}
$E \neq NE \Rightarrow P \neq NP$
\end{Korollar}
\paragraph{Slogan} Gleichheit von Komplexitätsklassen vererbt sich nach oben; Ungleichheit vererbt sich nach unten.
\end{Satz}
\newpage
\section{Die Klassen P und NP}
\subsection{NP-Vollständigkeit}
\begin{Satz}[NP als Verifikation in polynomieller Zeit]
Wenn $L \in \NP$ dann gibt es $R_L \in P$ und $k \in \N$ so dass $x \in L \Leftrightarrow$
es existiert $w$ mit $(x,w) \in R_L$ und $|w| \leq |x|^k$
\end{Satz}
\begin{beweis}
Deute $w$ als 'Beweis' für $x \in L$. Aussage des Satzes ist, dass für Sprachen in $\NP$ immer ein Beweisbegriff existiert,
sodass Korrektheit eines Beweises in polynomieller Zeit geprüft werden kann.\\
Sei $L \in \NP$ und $\NTIME_T(x) \leq |x|^k$ wobei $T$ eine Nichtdeterministische Turingmaschine für $L$ ist.\\
ObdA habe der Berechnungsbaum von $T$ auf $x$ Verzweigungsgrad 2.\\
$R_L= \lbrace (x,w) \mid w \in \lbrace 0,1 \rbrace ^*$, der durch $w$ ausgewiesene Zweig im Berechnungsbaum von $T$ auf $x$ akzeptiert $\rbrace$\\

Klar ist $R_L \in \Pol$ (nichtdet. Entscheidung werden ja gemäß $w$ vorgenommen)\\
Falls $x \in L$ so wähle einen akzeptierenden Pfad der Länge $\leq |x|^k$. Setze für $w$ das entsprechende Wort aus ${0,1}^*$. Es gilt
$(x, w) \in R_L$ und $|w| \leq |x|^k$.\\

Falls $(x,w) \in R_L$ und $|w| \leq |x|^k$ so gilt $x \in L$ nach Definition von $R_L$
\end{beweis}
\begin{Definition}[NP-schwer]
Eine Sprache $L \subseteq \Sigma^\ast$ ist NP-schwer, falls für jede Sprache $L' \in\NP$ eine in polynomieller Zeit berechenbare Funktion $f: \Sigma^\ast \to \Sigma^\ast$ existiert, sodass $x \in L' \Leftrightarrow f(x) \in L$.
\end{Definition}
\begin{Definition}[Transducer]
Ein Transducer (Übersetzer) ist eine deterministische TM mit zwei ausgezeichneten Bändern (ein Eingabe- und ein Ausgabeband). Ein Transducer berechnet eine Funktion $f: \Sigma^\ast \to \Sigma^\ast$, wenn die Maschine T für alle Eingaben $x \in \Sigma^\ast$ hält und dann auf dem Ausgabeband das Wort $f(x)$ steht. Man sagt ''T berechnet f''. DTIME wird analog auch für Transducer definiert.
\end{Definition}
\begin{Definition}[FP formal]
$f \in\FP$ gdw.\ es einen Transducer T, der f berechnet, und es existiert ein Polynom $p$, so dass $\TIME(T(x))\leq p(|x|)$.
\end{Definition}
\begin{Beispiel}
$f(x) = x^2$ (x eine Zahl in Binärnotation)\\
$f(x) =$ Tabelle der kürzesten Wege von einem Startknoten s in einem gerichteten Graphen G, wobei G und s durch x codiert sind.\\
$f(x) = 2^x$ ist nicht in \FP\\\\
N.B. Falls $f \in\FP$ dann gilt $|f(x)| \leq p(|x|)$ für ein festes Polynom p.
%
% (Ende Ergaenzung S. Goebl)
%
\end{Beispiel}
\begin{Definition}[SAT Problem]
Gegeben: aussagenlogische Formel q\\
Gefragt: Ist q erfüllbar (gibt es Belegung der Variablen, die q wahrmacht)
\end{Definition}
\begin{Definition}[3-COL]
Die Sprache 3-COL besteht aus allen ungerichteten Graphen $G= (V,E)$ die mti drei Farben gefärbt werden können, d.h. es existiert $c: V \to \{r,g,b\}$ sodass:\\
$\{v, v'\} \in E \To c(v) \ne c(v')$
\end{Definition}
\begin{Satz} Es gibt eine Funktion $f \in FP$ sodass $x \in$ 3-COL \Gdw f(x) $\in$ SAT
\end{Satz}
%%%%%%%%%%%%%%%%%%% 
\begin{beweis}
%% Begin Beweis%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%
 Sei $x \in (V,E)$ Graph\\
 $f(x)$ ist wie folgt definiert:\\
 Für jeden Knoten $v \in V$, für jede Farbe $c \in \{r,g,b\}$ eine Variable $x_{v,c}$ Das macht insgesamt $3 \cdot |v|$ Variablen\\
 Für jeden Knoten v die Formel $x_{v,r} v x_{v,b} v x_{v,g}$ /* |v| Formeln\\
 Für jeden Knoten v die Formel $\neg (x_{v,r} \land x_{v,b}) \land \neg  (x_{v,r} \and x_{v,g}) \land \neg  ( x_{v,b} \land x_{v, g})$ /* |V| Formeln /*\\
 Für $\{v, v'\}\in E: \neg  (x_{v,r} \land x_{v', r}) \land \neg  (x_{v, g} \land x_{v', g} ) \land \neg  ( x_{v,b} \land x_{v',b})$\\
 f(x) besteht aus konjunktion all dieser Formeln ($2 \cdot |V| + |E|$ Stück )\\
 $f(x)$ erfülbar \Gdw $x \in$ 3-Col
\\
Man schreibt 3-Col $\leq_P$ SAT
%%%%%%%%%%%%%%%%%
\end{beweis}
\begin{Satz}[Satz von Cook-Levin]
SAT ist NP-vollständig
D.h. für jede Sprache $L\in\NP$ gibt es eine Übersetzungsfunktion $f \in FP$ welche Instanzen von L auf aussagenlogische Formeln abbildet, sodass $x \in L \Gdw f(x)$ erfüllbar
\end{Satz}

%%%%%%%%%%%%%%%%%%%
\begin{Beweis}
(Skizze) 

 Sei $L \in$ NP und T eine NTM mit L = L(T) und $\NTIME(T(x)) \leq p(|x|)$ für ein Polynom p\\
 Wir müssen eine Funktion f konstruieren, sodass $x \in L \Gdw f(x) erfüllbar$. 
Erinnerung: $x \in L$ \Gdw in Berechnungsbaum von T auf x ein akzeptierender Pfad existier, bzw, wenn ausgehend von der Startkonfiguration $S_0$ von T auf x eine Folge von Konfigurationen $S_0 \to S_1 \ldots \to S_n$ existiert, sodass $S_n$ akzeptierend ist und $'\to'$ Übergangsrelation von T ist \\
ObdA : $n = p(|x|)$ und T hat nur ein Band\\
f(x) ist jetzt wie folgt definiert:\\
Variablen:\\
Für alle $t \leq p(|x|), q \in Q$ eine Variable $zust_{q,t}$ /* T ist zur Zeit t im Zustand q, O(p(|x|)) Stück */ \\
Für alle $i \leq p(|x|), t \leq p(|x|), a \in \Sigma$ eine Variable $sym_{a,i,t}$ /* zur Zeit t steht an Position i das Symbol a, $O(p(|x|)^2)$ Stück */\\
Für alle $z,t \leq p(|x|)$ eine Variable $kopf_{i,t}$ /* Zur Zeit t ist der Kopf an Position i */\\
Formeln welche ausdrücken, dass die Belegung dieser Variablen einer legalen akzeptierenden Berechnung entspricht:\\
Z.B.\ $\Land_{i \leq p(|x|)} sym_{x_i, i, 0}$ Wobei $x = x_0 \ldots x_{m-1}\\
\Land_{i \geq |x|} sym_{\square,i , 0}\\
\Land_{i \geq p(|x|, a \ne a', t \leq p(|x|)} \neg (sym_{a,i,t} \Land sym_{a', i, t})$\\
Für jeden Zustand q und Symbol a Zeitpunkt t, Position i die Formel\\
$zust_{q,t} \land kopf_{i,t} \land symbol_{a,i,t} \To \lor_{(q, a, q', a',d) \in I} zust_{q', t+1} \land kopf_{i+d,t+1} \land sym_{a', i, t+1}\\
\ldots$ \\
Idee: Die Variablen von $f(x)$ beschreiben Folgen von globalen Konfigurationen von T der Länge und Größe $p(|x|)$\\
Die Formeln von $f(x)$ beschreiben, dass solch eine Folge akzeptierend ist. Die Konjunktion dieser Formeln ist dann erf"ullbar, genau dann, wenn eine akzeptierende Berechnung existiert. 
\end{Beweis}
Weite NP-vollständige Probleme:\\
3-COL, TSP, Hamiltonsche Kreise, $\ldots$\\
\begin{Definition}[NP-Schwer]
 Ein Problem/Sprache L ist NP-schwer wenn $L' \leq_P L$ für alle $L' \in \NP$
\end{Definition}
\begin{Definition}[NP-vollständig]
Eine Sprache L ist NP-vollständig, wenn $L \in \NP$ und L NP schwer
\end{Definition}
\begin{Bemerkung} 
Könnte man ein NP-vollständiges Problem in polynomieller Zeit lösen, so wäre NP = P\\
Levin hat einen Algorithmus angegeben, der zu gegebener erf"ullbarer Formel in polynomieller Zeit eine erf"ullende Belegung findet, vorausgesetzt, dass $P=NP$ (Levin-search). 
\end{Bemerkung}
\subsection{Satz von Ladner}
\begin{Theorem}[Satz von Ladner]
Es gibt eine Sprache $L \in \NP$ die nicht NP-vollständig ist und trotzdem nicht in P liegt.\\
Das natürlich unter der Voraussetzung $\Pol \ne  \NP$.
\end{Theorem}
%%%%%%%%%%%%%%%%%%% 
\begin{beweis}
%% Begin Beweis%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%
 Beginne mit NP-vollständiger Sprache $L_0$ z.B $L_0 =$ Sat wähle $w_0 \notin L_0$\\
 Ansatz:\\
$ L = \{x \in L_0 \mid |x| \in G\}$ f"ur noch zu bestimmendes $G$. 
 \\
 $f(x) = \begin{cases} x &\text{ falls }|x| \in g \\ w_0 &\text{ falls |x| }\notin G\end{cases}$
 \\Es gilt $x \in L \gdw f(x) \in L_0$
 \\
 Ziel: 
 \begin{enumerate}
\item 
Wähle $G$ so, dass $f \in \FP$ , dazu muss $|x| \in G$? in polynomieller Zeit entscheidbar sein. Dann ist zumindestens $L \in \NP$, da $L \leq_P L_0$ vermöge f und $L_0$ NP-vollständig
\item
Wähle G so dass $L \ne$ i-te Sprache in $\P$\ und außerdem $L \ne$ i-te Sprache die NP-vollständig ist. Dies für alle $i \geq 0$
\end{enumerate}
%%%%%%%%%%%%%%%%%



%%
%%
%%% Vorlesung 30.10.2008
%%%
Sei $T_1, T_2, T_3 \ldots$ eine Aufzählung von Turingmaschinen, so, dass 
\[
\Pol = \{L(T_i) \mid i\geq 0\}
\]
Außerdem soll $i \mapsto T_i$ berechenbar sein.\\

\underline{Idee:}\\
Gegeben:\\
Decodiere i als Tupel $(T,p)$ wobei T eine TM ist und p Polynom\\
bei falschem Format setze $T_i = 0$ /* Default Maschine */
Setze $T_i :=$ Die Maschine, die auf Eingabe $x$ die Berechnung von $T(x)$ für $p(|x|)$ Schritte simuliert und akzeptiert gdw.\ die Simulation akzeptiert hat.'\\
\\
Sei $T_1', T_2', \ldots$ eine Aufzählung von Turingmaschinen, so dass $\NPC = \{L | \exists i: T_i'$ entscheidet $L$\}\\
Idee: gegeben i:\\
Decodiere i als Tupel (T,f)\\
T nichtdet.\ TM polynomieller Laufzeit\\
f ist FP-Transducer\\
Konstruiere aus  $T,f$ folgende deterministische TM $T_i'$\\
Bei Eingabe $x$ prüfe zunächst, ob 
$y\in \text{SAT}\iff f(y)\in L(T)$ für alle $y$ mit $|y|\leq|x|$.  (durch Brute-Force Simulation aller Berechnungspfade). 
Falls Ja: Akzeptiere, gdw.\ $x\in L(T)$ \\
Falls Nein: Akzeptiere, gdw.\ $x\in\text{SAT}$
\\\\
Ist $i=(T,f)$ und $L(T)$ NP-vollst"andig vermöge der Reduktion $f$, so gilt $L(T_i')=L(T)$. Anderenfalls unterscheidet sich $L(T_i')$ nur an endlich vielen Punkten von SAT und ist somit immerhin NP-vollst"andig. \\\\

Sei nunmehr $L_i=L(T_i)$ und $L_i'=L(T_i')$. Es ist $\Pol=\{L_i\mid i\geq 0\}$ und $\NPC=\{L_i'\mid i\geq 0\}$. Hier ist $\NPC$ die Menge der NP-vollst"andigen Sprachen. \\\\
\underline{Ziel:} Konstruiere $G \subset \N$ so, dass $\forall i  L^\ast \ne L_i$ und $L^\ast \ne L_i'$\\
\ruck{NB} {
A,B Mengen: $A \ne B$ falls $A \Delta B \ne\emptyset$ wobei $A \Delta B = A \setminus B \cup B \setminus A$}
Für jedes $n,i \in \N$ gibt es ein Wort x mit $|x| \geq n$ so dass
$x \in L \Delta L_i$
\ruck{NB} {$x$ bezeugt, dass $L \ne L_i$}
Nach Voraussetzung $\Pol \ne  \NP$ muss $L \Delta L_i \ne \emptyset$ sein\\\\

Mehr noch: f"ur jedes $n$ gibt es $y\in L\Delta L_i$ mit $|y|\geq n$, denn sonst w"urde sich $L$ nur an endlich vielen Punkten von $L_i$ unterscheiden und w"are damit selbst in $\Pol$. \\\\

Für jedes $i, n \in \N$ gibt es au"serdem $y$
 mit $|y| \geq n$ und $y \in L_i'$\\
Sonst wäre nämlich $L_i'$ endlich und deshalb in \Pol. Wegen der 
Voraussetzung $\Pol \ne \NP$ kann eine NP-vollständige Sprache wie $L_i'$ nicht in \Pol\ sein\\
Sei nun $r$ zeitkonstruierbare funktion $r: \N \to \N$, sodass für alle $n \in \N$ sodass für jedes $i \leq n$ ein Wörter $x\in L\Delta L_i$ und $y\in L_i'$ mit   mit $n\leq |x|,|y|\leq r(n)$ existieren. 
\underline{Idee:}\\
Gegeben n:\\
Simuliere alle $T_i, T_i'$ mit $i \leq n$ auf allen Eingaben der Längen , $n, n+1, n+2, \ldots $ solange bis  passende Wörter $x$ und $y$ gefunden sind. Nach vorhergehender Diskussion gibt es solche.\\
Ausgabe: Rechenzeit dieses ganzen Prozesses.\\\\
Dahinter steckt die allgemeine Beobachtung:\\
Zu jeder berechenbaren Funktion f gibt es eine zeitkonstruierbare Funktion g mit $g(n) \geq f(n)$\\
Setze nun:\\
 $r_0 = 0\\
r_1 = r(0) +1\\
r_2 = r(r_1) +1\\
\vdots\\
r_{n+} = r(r_n) +1$
$$G = \{n | r_i \geq n < r_i+1\text{ wobei i gerade }\}$$
\ruck{Erinnerung}{ 
$L^\ast = \{x \in L | |x| \in G\}$
}
\underline{Behauptung:} $L^\ast \notin\NPC$\\
Wäre $L^\ast = L_i'$ für ein i, dann wähle n ungerade, sodass $r_n \geq i$\\
Im Bereich $r_n \ldots r(r_n)$ findet sich ein $y \in L_i'$ Nach Definition von G ist aber $y \notin L^\ast$ weil $|y| \notin G$\\
\underline{Behauptung:} $L^\ast \notin$ P: \\
Wäre $L^\ast = L_i$ für ein i dann wähle n gerade,  sodass $r_n \geq i$. Im Bereich $r_n, \ldots, r(r_n) = r_{n+1} -1$ findet sich ein $x \in L_i \Delta L$. Auf diesem Bereich stimmen $L$ und $L^\ast$ überein. Also ist $x \in L_i \Delta L^\ast$\\
Es folgt $L_i \ne L^\ast$\\[.2cm]
Es bleibt zu zeigen, dass: $\{x | x \in G\} \in P$\\
Gegeben: x\\
Berechne sukzessive $r_0, r_1, r_2, \ldots$\\
bis n gefunden ist mit $r_n \geq |x| < r_{n+1}$\\
akzeptiere \Gdw n gerade\\
Die Berechnung eines $r_i$ verbraucht Zeit $\Ocal( r_i)$\\
also nachdem alle $r_i \leq |x|$ sind: $\Ocal(|x|)$\\
Außerdem kann n (sehr grob) durch |x| abgeschätzt werden\\
\To Gesamtlaufzeit $\Ocal(|x|^2)$
%%%%%%%%%%%%%%%%%
\end{beweis}%%%%%%%%%
%% End Beweis%%%%%%%%%
%%%%%%%%%%%%%%%%%

Bis heute wurden keine konkreten Sprachen echt zwischen \Pol\ und \NPC\ gefunden.\\
\underline{Immerhin}:\\
Definiert man $co-\NP := \{ L | \strich{L} \in \NP\}$\\
Dann ist $\NP = co-\NP$ ein offenes Problem und auch ob:\\
$\Pol = \NP \cap co-\NP$\\
Falls $NP \ne co-\NP$, so ist kein Problem in $co-\NP$ auch NP-vollständig. 

%%
%% Vorlesung 3.11.2008
%%
\subsection{Orakelmaschinen}
\begin{definition}[Orakelmaschine]
Eine (nicht)deterministische Orakelturingmaschine ist eine (nicht)deterministische TM T mit drei ausgezeichneten Zuständen $q_Q, q_Y, q_N$\\
Falls $C \subset \Sigma^\ast$, so definiert man die \vip{Berechnung} von T auf Eingabe $x \in \Sigma^\ast$ ($T^C(x)$)wie folgt:\\
$T^C(x)$ erfolgt wie 'normal' mit der folgenden Ausnahme:\\
gelangt die Berechnung in den Zustand $q_Q$ (query) so wird die Berechnung im Zustand $q_Y$ fortgesetzt falls 'Bandinhalt' (des ersten Bandes)$\in C$\\
und in $q_N$ fortgesetzt, falls 'Bandinhalt' $\notin C$\\[.3cm]
$L(T^C) = \{x | T^C(x)$ akzeptiert \}\\
bzw. $L(T^C) = \{x$ | es gibt eine akzeptierende Berechnungsfolge im Baum $T^C(x)$\}
\end{definition} 
%%


\begin{definition}
Sei $C \subset \Sigma^\ast$ Wir definieren:
\[
\begin{array}{ll}
\Pol^C = \{L \mid 
&\text{es existiert  det.\ Orakel TM $T$, $L = L^C(T)$ und Polynom $p$:}\\ 
&\text{die Länge der
Berechnung $T^C(x)$ ist durch $p(|x|)$ beschränkt.}\}
\end{array}
\]
\end{definition}
\begin{bemerkung}
Falls $L \in \Pol$, z.B. L = Addition, Matching, $\ldots$\\
so ist $\Pol^L = \Pol$\\
Begründung:\\
Simuliere Berechnung $T^L(x)$ durch eigenständige Beantwortung der Orakelanfragen.
\end{bemerkung}
\begin{bemerkung}
Lautzeit von T beschränkt durch p und $L \in \TIME(q)$ für Polynom q\\
\To Laufzeit der Simulation beschränkt durch $p(n) \cdot q(\underbrace{p(n)}_{\text{Schranke an die Länge der Anfrage}})$
\end{bemerkung}
\begin{bemerkung}
$\NP \subset \Pol^{SAT}$ ist klar. Die Frage, ob $\NP \supset \Pol^{SAT}$ ist ein offenes Problem. 

Setzt man $TAUT = \{\phi \mid \phi\text{ allgemeingültig}\}$, so folgt TAUT$ \in \Pol^{SAT}$ mit folgender Maschine: \\\\
Eingabe: q /* q aussagenlogische Formel */\\
Frage ob $\neg q \in SAT$ /* Schreibe $\neg q$ aufs erste Band gege in $q_Q$ */\\
Falls ja: REJECT\\
Falls nein: ACCEPT\\[.3cm]
Aber $TAUT \in NP$ ist ein bekanntes offenes Problem. 
\end{bemerkung}
\begin{definition}
Sei $C \subset \Sigma^\ast$ Wir definieren:\\
\[
\begin{array}{ll}
\NP^C = \{L \mid 
&\text{es existiert  nichtdet.\ Orakel TM $T$, $L = L^C(T)$ und Polynom $p$:}\\
&\text{die Laufzeit der Berechnung $T^C(x)$ ist durch $p(|x|)$ beschränkt.}\}
\end{array}
\]
\end{definition}
\begin{bemerkung}
$P^C \subset NP^C$
\end{bemerkung}
\begin{bemerkung}
Die Sprache $\{(\vieh,U) \mid \vieh$ auss.log. Formel, $U$ Teilmenge der Variablen, es existiert Belegung $\eta$ der Variablen in $U$, sodass $\vieh[\eta]$ allgemeingültig ist$\}$ ist in  $\NP^{SAT}$. (Rate Belegung der Variablen in $U$, entscheide mit SAT-Orakel, ob entstehende Formel allgemeingültig ist.) 
\subsection{Relativierungen von P und NP}
Es ist ein offenes Problem, ob diese Sprache in $\Pol^{SAT}$ ist. 
\end{bemerkung}
\begin{theorem}
Es gibt eine Sprache $C \subset \Sigma^\ast$, sodass $\Pol^C = \NP^C$
\end{theorem}
\begin{bemerkung}
Es ist unbekannt ob $\Pol^{SAT} = \NP^{SAT}$
\end{bemerkung} 
\begin{beweis}
$C = \{(T,x,0^k) \mid T$ ist det.\ TM und $T(x)$ akzeptiert und verbraucht höchstens $k$ Bandpositionen (zusätzlich zur Eingabe)\}\\\\
\underline{NB:} C ist entscheidbar. Es gibt n"amlich nur $2^{poly(k,|x|)}$ viele m"ogliche globale Konfigurationen. Hat die Berechnung nach dieser Zeit nicht gehalten, so h"alt sie "uberhaupt nicht mehr und kann abgebrochen werden. \\\\
\underline{NB:} Es ist offen ob $C \in \Pol$\\
$P^C\subset NP^C$ ist klar.\\\\
Es bleibt zu zeigen $NP^C \subset P^C$\\
Sei $T$ nichtdet.\ Orakel TM zeitbeschränkt durch Polynom $p$.
Wir konstruieren eine deterministische polynomialzeitbeschränkte Orakel TM $T'$ mit $L(T^C) = L(T'^C)$ und $T'$
 tätigt nur eine einzige Orakelanfrage ganz am Ende.\\
$T'$ wie folgt:\\
EINGABE: x\\
Baue eine det.\ TM  $T_0$, die $T^C(x)$ ohne Benutzung des Orakels
 simuliert. Dies durch systematische Exploration aller Berechnungspfade und Beantwortung aller Orakelanfragen durch obenstehende Entscheidunsprozedur\\
Man kann diese Maschine so konstruieren, dass sie nur $p'(|x|)$ Bandzellen anfordert für ein Polynom $p'$\\
Frage nun, ob $(T_0,x, 0^{p'(|x|)}) \in C$\\
Falls ja, akzeptiere\\
Falls nein verwerfe.\\
NB: Laufzeit dieser Maschine ist polynomiell, denn sie setzt sich zusammen aus folgendem: Erzeugung des Codes für $T_0$,  Erzeugung von $0^{p'(|x|)}$ und stellen der Anfrage an $C$.
\end{beweis}
\begin{bemerkung}
Eine Beweismethode wie z.B.\ Diagonalisierung, die in Gegenwart von Orakeln funktioniert kann nicht P von NP trennen.
\end{bemerkung}
\begin{satz}
Es existiert eine Sprache $C \subset \Sigma^\ast$ sodass $P^C \ne NP^C$

\end{satz}
\begin{bemerkung}[Vorbemerkung zum Beweis] Ist T eine OTM, $C \subset
  \Sigma^\ast$ und wird die Anfrage y in der Berechnung $T^C(x)$ nicht
  gestellt, dann gilt: $T^C(x)$ akzeptiert \Gdw $T^{C \setminus
    \{y\}}(x)$ akzeptiert \Gdw $T^{C \cup \{y\}}(x)$ akzeptiert
\end{bemerkung}
\begin{beweis}
Sei  $T_0, T_1, \ldots $ eine effektive Aufzählung von polynomialzeitbeschränkten OTM sodass gilt:\\
\begin{enumerate}
\item 
$P^C = \{ L^C(T_i) \mid i \geq 0 \}$ für alle C
\item
Laufzeit von $T_i^C(x) \leq |x|^i + i$

\end{enumerate}
Übung: Solche Aufzählung existiert\\
Wähle $B \subset \Sigma^\ast$ in noch zu bestimmender, geeigneter Weise\\
C = \{$0^n$ | es existiert $x \in B$ mit |x| = n\}\\
Es gilt $C \in NP^B$ ganz egal was $B$ am Ende ist:\\
Gegeben $0^n$, rate $x \in \Sigma^\ast$ mit $|x| = n$. Frage dann das Orakel, ob $x \in B$\\
Wir werden es so einrichten, dass $C \ne L^B(T_i)$ für jedes i und somit $C \notin P^B$\\
%%%
%%%Vorlesung 10.11.2008
%%%
$B_0 = \emptyset, n_0 = 0$\\
Seien $B_i$ und $n_i$ schon definiert. Wir legen $B_{i+1}, n_{i+1}$ wie folgt fest:\\ /* Invariante: $B_i$ enthält kein Wort der Länge $\geq n_i$ */\\
/* Invariante: $2^{n_i} > n_i^i + i- 1$ */\\
Rechne $T_i^{B_i}(0^{n_i})$ /* Dauert $n_i^{i} + i$ Schritte */\\
Falls akzeptiert wird: $B_{i+1} := B_i$, sodass $0^{n_i} \notin C$\\
Falls zurückgewiesen wird: \\
\phantom{tztz}\begin{tabular}{l}
Wähle $w$ mit $|w| = n_i$ und so dass $w$ in obiger Berechnung \\ nicht gefragt wurde. So ein $w$ muss es wegen der Wahl von $n_{i}$ geben.
\\Setze $B_{i+1} := B \cup \{w\}$\end{tabular}

\noindent
Wähle $n_{i+1}$ so dass
\begin{itemize}
\item
$2^{n_{i+1}} > n_{i+1}^{i+1} + i+1$
\item
$n_{i+1} > n_i^{i} +i -1$
\end{itemize}

\bigskip

Setze nun: $B = \bigcup_{i\geq0} B_i$. 
Mit dieser Wahl von $B$ gilt:\\
$C \notin P^B$. Denn wäre $C = L(T_i^B)$ für  ein $i \geq 0$, dann betrachten wir die Berechnung $T_i^B(0^{n_i})$. Aufgrund der Konstruktion kommt hierbei dasselbe Ergebnis heraus wie bei der Berechnung $T_i^{B_i}(0^{n_I})$. Es gilt aber $0^{n_i} \in L(T_i^{B_i}) \Gdw 0^{n_i} \notin C$\\
Also ist $C \ne L(T_i^{B})$\\[.3cm]
Halbkonkrete Konstruktion der ersten 3 Schritte ($\Simga = \{0,1\}$):\\
Betrachte: $T_0^{B_0}(\epsilon)$ /* $B_0 = 0, n_0 = 0$ */\\
Falls akzeptiert: $B_1 = B_0 = \emptyset$ hier $\epsilon \notin C$  (wir nehmen an, dass dieser Fall eintritt)\\
Falls zurückgewiesen wird: $B_1 = \{\epsilon\}$ hier $\epsilon \in C$\\
$n_1$ sodass $2^{n_1} > n_1^1 + 1$ und $n_0^0 + 0$\\
$n_1 = 2$\\
Betrachte $T_1^{B_1}(00)$ Rechenzeit $2^1 + 1 = 3$ Schritte \\
Annahme. Die Berechnung weise zurück und das Wort 11 werde nicht angefragt.\\
$B_2 = \{11\}$\\
$n_2$ so dss $2^{n_2} > n_2^2 + 2$ und $n_2 > n_1^1 +1 = 3$\\
z.b: $n_2 = 5$\\
Betrachte $T_2^{B_2}(00000)$\\
Rechenzeit: 27 Schritte\\
Annahme: Die Berechnung weise zurück und frage das Wort $11011$ nicht an. Dann setzen wir $B_3 = \{11, 11011\}$\\
$n_3$ sodass $2^{n_3} > n_3^3 + 3$ und $n_3 > 27$\\
z.B.: $n_3 = 28$
\end{beweis}
\subsection{Die Polynomielle Hierarchie}
$\NP^{\operatorname{SAT}}$ ist mehr als $\NP$. Es gilt sogar $\operatorname{TAUT} \in \Pol^{\operatorname{SAT}} \subset \NP^{\operatorname{SAT}}$ aber $\operatorname{TAUT}$ ist co-\NP\ vollständig.\\
Die Komplexitätsklasse $\NP^{\operatorname{SAT}}$ wird mit $\Sigma^{\Pol}_2$ bezeichnet, die Klasse $\Pol^{\operatorname{SAT}}$ wird mit $\Delta_2^{\Pol}$ bezeichnet.
\begin{Definition}[polynomielle Hierarchie]
$\Sigma_0^{\Pol} = \Delta_0^{\Pol} = \Pi_0^{\Pol} := \Pol$ /* Polynomialzeit */\\
$\Sigma_{i+1}^{\Pol} = \NP^{\Sigma_i^{\Pol}} = \bigcup_{C \in \Sigma_i^{\Pol}} \NP^C$\\
$\Delta_{i+1}^{\Pol} = P^{\Sigma_i^{\Pol}}$\\
$\Pi_{i+1}^{\Pol} = \operatorname{co-NP}^{\Sigma_i^{\Pol}}$
\end{Definition}
\begin{bemerkung}
Es gilt:\\
$\NP = \Sigma_1^{\Pol}$ \\
$\operatorname{co-NP} = \Pi_1^{\Pol}$\\
$\Pol^{\operatorname{SAT}} = \Pol^{\NP} = \Delta_2^{\Pol}$\\
$\NP^{\operatorname{SAT}} = \Sigma_2^{\Pol}$\\
Offensichtlich gelten folgende Inklusionsbezeichnungen als Hasse Diagramm:

\begin{tabular}{ccc}
&$\vdots$&\\
& $ \Delta_3^{\Pol}$ \\
/ & & $\setminus$\\
$\Pi_2^{\Pol}$ & & $\Sigma_2^{\Pol}$\\
 $\setminus$ & & / \\
& $ \Delta_2^{\Pol}$ \\
/ & & $\setminus$\\
$\Pi_1^{\Pol}$ & & $\Sigma_1^{\Pol}$\\
 $\setminus$ & & / \\
& $ \Delta_1^{\Pol}$ \\
/ & & $\setminus$\\
$\Pi_0^{\Pol}$ & & $\Sigma_0^{\Pol}$\\
 $\setminus$ & & / \\
& $\Delta_0^{\Pol}$
\end{tabular}
\end{bemerkung}
\begin{bemerkung}[Notation]
Für $n \in \N$ schreiben wir \\
$\exists_n y. \varphi(y)$ für $\exists y \in \Sigma^\ast. |y| \leq n \land \varphi(y)$\\
$\forall_ny. \varphi(y)$ für $\forall y \in \Sigma^\ast. |y| \leq n \To \varphi(y)$
\end{bemerkung}
\begin{satz}\label{quan}
$L \in \Sigma^{\Pol}_i$ genau dann wenn eine Sprache $A \in \Pol$ und ein Polynom $p$ existiert, sodass:\\
$x \in L \Gdw \exists_{p(|x|)} y_1 \forall_{p(|x|)} y_2 \exists_{p(|x|)}y_3 \ldots \exists/\forall_{p(|x|)} y_i (x,y_1, y_2, \ldots, y_i) \in A$\\
Analog gilt $L \in \Pi_i^{\Pol}$ \Gdw es gibt Sprache $A \in \Pol$ und Polynom $p$ mit\\
$x \in L \Gdw \forall_{p(|x|)} y_1 \exists_{p(|x|)} y_2 \ldots (x, y_1, \ldots, y_i) \in A$
\end{satz}
\begin{beweis}
durch Induktion über $i$. Wir führen nur die Fälle $i=0,1,2$ durch.\\
$i=0$ Klar\\
$i=1$ Aussage des Satzes:\\
$L \in \Sigma_1^{\Pol}$, d.h. $L \in \NP \Gdw$ eine Sprache $A \in \Pol$ und ein Polynom $p$ existiert sodass:\\
$x \in L \Gdw \exists y_1: |y_1| \leq p(|x|) \land (x,y_1) \in A$\\
Dies wurde bereits bewiesen.\\
$i=2$:\\
Aussage des Satzes:\\
$L \in \Sigma_2^P$, d.h. $\NP^{\operatorname{SAT}}$ \Gdw eine Sprache $A \in \Pol$ und ein Polynom $p$ existieren mit: $L = \{x \mid \exists_{p(|x|)} y_1.\forall_{p(|x|)}y_2.(x,y_1,y_2) \in A$\} \\
\underline{\oT}:\\
Sei $L = \{x \mid \exists_{p(|x|)} y_1.\forall_{p(|x|)}y_2.(x,y_1,y_2) \in A$\} für ein $A \in P$ und Polynom p\\
Wir sollen zeigen $L \in \NP^{\NP}$\\
Es gilt $x \in L \Gdw$ \\
$\exists_{p(|x|)} y_1.\neg \underbrace{\exists_{p(|x|)} y_2.\underbrace{(x,y_1,y_2) \notin A}_{\in \Pol}}_{=: B(x,y_1) \in \NP}$\\
Offensichtlich:\\
$B \in \NP$ und $L \in \NP^B \subset \NP^{\NP}= \Sigma_2^{\Pol}$\\
\underline{\To:}\\
Sei eine Orakelmaschine T vorgelegt sodass $L = L(T^{\operatorname{SAT}})$ und sei $T$ nichtdet und polynomiell zeitbeschränkt. Wir müssen eine Sprache $A \in P$ finden sodass\\
$L = \{x \mid \exists_{p(|x|)}  y_1.\forall_{p(|x|)}y_2.(x,y_1,y_2) \in A$ \}\\
Es gilt $x \in L \Gdw$ es existiert eine Folge von Konfigurationen $y$ von $T$ auf {Eingabe $x$}, sodass,  falls {$z = z_1 z_2 \ldots z_k$} die in $y$ getätigten und positiv beantworteten  Anfragen an das $\operatorname{SAT}$ Orakel bezeichnet und falls  {$w = w_1 w_2 \ldots w_k$} die in $y_1$ getätigten und negativ beantworteten  Anfragen an das $\operatorname{SAT}$ Orakel bezeichnet, folgendes gilt: 
\begin{itemize}
\item alle Rechenschritte in $y_1$ erfolgen gemäß T 
\item alle $z_1 \ldots z_k \in \operatorname{SAT}$ /* das ist von der Form $\exists y_1' \ldots$ */
\item alle $w_1 \ldots w_l \notin \operatorname{SAT}$ /* das ist von der Form $\forall y_2 \ldots $ */

\end{itemize}
Die gewünschte Charakterisierung lässt sich daraus ablesen.\\Beachte: zwei aufeinanderfolgende polynomiell beschränkte Existenzquantoren können durch einen einzigen ersetzt werden.
\end{beweis}
%\begin{satz}[Karp-Lipton]
%Falls es polynomiell große Schaltkreise für SAT gibt so folgt$\Sigma_2^{\Pol} = \Sigma_3^{\Pol}$\\
%und daraus folgt, dass $\Sigma_n^{\Pol} = \Sigma_2^{\Pol} ~~\forall n \geq 2$, d.h. PH kolabiert auf die zweite Stufe
%\end{satz}
%\begin{beweis}
\paragraph*{Abstrakte Notation}
\begin{itemize}
\item
$\varphi, \psi$ bezeichnen Formeln (Boolesch)
\item
$|\varphi|, |\psi|$ bezeichnet Länge der Formel
\item
$\eta, \eta'$ bezeichnet Belegung (codiert)
\item
$\eta \models \varphi$ : Belegung $\eta$ erfüllt Formel $\varphi$\\
Klar: $\{ (\eta, \varphi) \mid\eta \models \varphi\} \in P$\\
$\operatorname{SAT} = \{\varphi \mid\exists \eta : \eta \models \varphi\} = \{ \varphi | \exists \eta. |\eta| \leq |\varphi| \land \eta \models \varphi\}$
\item
$C,C'$ bezeichne Schaltkreise\\
$|C|, |C'|$ deren Länge bzgl fester sinnvoller Codierung
\item
$C(\varphi)$ bezeichne die Anwendung von C auf (codierung von) $\varphi$\\
Klar: $\{(C, \varphi) \mid C(\varphi) = \true \}\in \Pol$
\end{itemize}
Betrachte: \\
Test-SAT = $\{(C, 1^n) \mid  C$ hat $n$ Eingabedrähte und für alle Formeln $\varphi$ der Länge $n$ gilt: $C(\vieh) = \true \Gdw \vieh \in \operatorname{SAT}\}$\\
Offensichtlich gilt $\operatorname{Test-SAT} \in \Pi_2^{\Pol}$, denn\\
$(C,1^n) \in \operatorname{Test-SAT} \Gdw\\
\forall \varphi : |\varphi| \leq n : (C(\varphi) = \true \lor \forall \eta.|\eta| \leq n \To \eta \not \models \varphi) \land (C(\varphi) = \false  \lor \exists \eta. |\eta| \leq n \To \eta \models \varphi) \\
\Gdw \forall_n \vieh \forall_n \eta \exists_n \eta' (C(\varphi) = \true \lor \eta \not \models \varphi) \land (C(\varphi) = \false \lor \eta' \models \varphi) $
\begin{lemma}[Selbstreduzierbarkeit von SAT]
$\operatorname{TEST-SAT} \in \Pi_1^{\Pol}$
\end{lemma}
\begin{beweis}
Betrachte folgenden offensichtlich polynomiellen) Algorithmus:\\
%Gegeben: $C, \varphi, n$:\\
%Seien $x_1, \ldots x_k~~~k\leq n$ die Variablen in $\varphi$\\
%Bilde $\varphi[x_1:= \true], \varphi[x_1:= \false]$ uns berechne $C(\varphi[x_1:= \true]), C(\varphi[x_1:= \false])$
Eingabe: $(C, \varphi, n)$\\
$x_1, \ldots,x_n$ die Variablen von $\varphi$\\
IF $C(\varphi) = \false$ RETURN 'Angeblich unerfüllbar'\\
ELSE /* $C(\vieh)=\true$*/ wähle $b_1 \in \{\true, \false\}$ sodass $C(\varphi[x_1:=b_1] = \true$\\
falls nicht existent RETURN 'Widerspruch!'\\
$\vdots$\\
wähle $b_k \in \{\true, \false\}$ sodass $C(\vieh[x_1:=b_1, \ldots , x_k := b_k]) = \true$\\
falls nicht existent RETURN 'Widerspruch!'\\
IF $[x_1 \mapsto b_1, \ldots , x_k \mapsto b_k] \models \varphi$ return 'erfüllbar'\\
ELSE RETURN 'Widerspruch!'\\[.3cm]
Dieser Algorithmus erfüllt folgende Spezifikationen:\\
\begin{itemize}
\item
$A(C, \varphi, n) =$ 'Angeblich unerfüllbar' \Gdw $C(\varphi) = \false$
\item
$A(C, \varphi, n) =$ 'Widerspruch!' \To $\exists_n \psi.\neg(C(\psi) = \true \Gdw \psi\in\text{SAT}\}$
\item
$A(C, \varphi, n)$ = 'erfüllbar'  $\To \varphi \in \operatorname{SAT}$
\end{itemize}
\end{beweis}
Daraus folgt: $(C, 1^n) \in \operatorname{TEST-SAT} \Gdw \forall_n \varphi\\
(C(\varphi) = \false \land \forall_n \eta. \eta\not \models \varphi ) \lor (C(\varphi) = \true \land A(C, \varphi, n) = '$erfüllbar$'$). 

Das aber ist nach Satz~\ref{quan} in $\Pi^P_1$. 
%\end{beweis}

\begin{satz}[Karp-Lipton]
Falls ein Polynom p existiert derart dass $\forall n.\exists C . |C| \leq p(n). \operatorname{TEST-SAT}(C,1^n)$ (kurz : $\operatorname{SAT} \in \Pol/\operatorname{poly}$) dann folgt:\\
$\Sigma_2^{\Pol} = \Pi_2^{\Pol}$
\end{satz}
\begin{beweis}
Wir zeigen zun"achst: $\Pi^{\Pol}_2 \subseteq \Sigma_2^{\Pol}$:\\
Sei also $L \in \Pi_2^{\Pol}$ und $A \in \Pol$ und  $r$ Polynom sodass:\\
$x \in L \Gdw \forall_{r(|x|)}  y \exists_{r(|x|)} z (x,y,z) \in A$\\
Da $\operatorname{SAT}$ \NP-vollständig ist, gibt es eine Funktion $f \in \FP$ sodass:\\
$x \in L \Gdw \forall_{r(|x|)} y f(x,y) \in \operatorname{SAT}$. Letzteres ist aber "aquivalent zu 
$\exists_{p(q(|x|))} C. \operatorname{TEST-SAT}(C,1^{p(q(|x|))}) \land C(f(x,y)) = \true$\\
Hier ist $q$ so gewählt, dass $|y| \leq r(|x|) = |f(x,y)| \leq g(|x|)$\\
Nachdem $\operatorname{TEST-SAT} \in \Pi_1^{\Pol}$ ist folgt $L \in \Sigma_2^{\Pol}$\\
\\\\
F"ur die umgekehrte Richtung $\Sigma_2^{\Pol} \subset \Pi_2^{\Pol}$ argumentieren wir so: 
Falls $L \in \Sigma_2^{\Pol}$ dann ist $\strich{L} \in \Pi_2^{\Pol}$ also nach dem vorher Gezeigten ist $\strich L \in \Sigma_2^{\Pol}$ und also $L \in \Pi_2^{\Pol}$
\end{beweis}

Aus Satz~\ref{quan} ergibt sich auch unmittelbar, dass wenn $\Sigma^P_2=\Pi^P_2$, dann auch $\Sigma^P_i=\Sigma^P_2$ f"ur alle $i\geq 2$. Man sagt dann: die PH kollabiert auf die zweite Stufe oder k"urzer: die PH kollabiert. Der Satz von Karp-Lipton besagt also, dass sofern die PH nicht kollabiert, es  keine polynomiell großen Schaltkreise für $\operatorname{SAT}$ gibt.

\newpage
\section{Platzkomplexität}
\subsection{Grundlegende Definitionen}
\begin{definition}
  Bei platzbeschränkter Berechnung verwendet man Turingmaschinen mit mindestens zwei Bändern. Auf das erste Band wird die Eingabe geschrieben.\\
  Dieses Band darf während der Berechnung nicht verwendet werden. Der
  Platzbedarf $\operatorname{SPACE}(T(x))$ der Berechnung einer
  solchen Maschine $T$ auf Eingabe $x$ ist definiert als die Anzahl
  der Felder, die auf den verbleibenden Bändern benutzt werden.
\end{definition}
%
%%
%Vorlesung 17.11.2008
%%
% 
\begin{definition}[Platzkonstruierbare Funktion] $s: \N \to \N$
  platzkonstruierbar, falls TM existiert, die bei Eingabe $x$ auf
  Ausgabeband $1^{s(|x|)}$ ausgibt und dabei Platz $\Ocal(s(|x|))$
  verbraucht.
\end{definition}
\begin{beispiel}
$n, n^2, 2^n, \log n, n \log n$
\end{beispiel}
\begin{definition}
$\operatorname{DSPACE}(s(n)) = \{L \mid \exists$ DTM $T$ mit $L = L(T)$ und $\operatorname{SPACE}(T(x)) = \Ocal(s(|x|))\}$\\
$\operatorname{NSPACE}(s(n)) = \{L \mid \exists$ NTM $T$ mit $L = L(T)$ und $\operatorname{SPACE}(T(x)) = \Ocal(s(|x|))\}$\\
\end{definition}
\begin{bemerkung}
  Analog zur Zeitkomplexität gibt es auch für Platzkomplexität Hierarchiesätze, die in etwa besagen:\\
  Mit mehr Platz lässt sich auch beweisbar mehr berechnen.
\end{bemerkung}
\begin{satz}
$\operatorname{DSPACE}(s(n)) \subseteq \operatorname{DTIME}(2^{\Ocal(s(n))})\\
\operatorname{NSPACE}(s(n)) \subseteq \operatorname{DTIME}(2^{\Ocal(s(n))})$
\end{satz}
\begin{beweis}
Eine $s(n)$-platzbeschränkte TM hat $2^{\Ocal(s(n))}$ viele globale Konfigurationen.\\
In Zeit $\operatorname{DTIME}(2^{\Ocal(s(n))})$ kann die TM somit simuliert werden.
\end{beweis}
\begin{bemerkung}[triviale Beobachtung]
$\operatorname{DTIME}(t(n)) \subset \operatorname{DSPACE}(t(n))$
\end{bemerkung}
\begin{satz}
$\operatorname{DTIME}(t(n)) \subset \operatorname{DSPACE}( \frac {t(n)} {\log(n)})$\\
$\frac {t(n)} {\log n}$ platzkonstruierbar\\
$t(n)$ zeitkonstruierbar
\end{satz}
\begin{beweis}
siehe z.B.\  Skriptum von Goldreich
\end{beweis}
\begin{satz}
Falls $L$ durch $t(n)$ zeitkonstruierbare Einbandturingmaschine ber.\
 werden kann. so ist $L \in \operatorname{DSPACE}( \sqrt{t(n)})$ falls $t(n)$, $\sqrt{t(n)}$ zeitkonstruierbar sind und $t(n) \geq n^2$. 
\end{satz}
\begin{beweis}
siehe z.B.\ Bovet-Crescenzi
\end{beweis}
\begin{definition}[wichtige Platzklassen]
$\operatorname{LOGSPACE}$ (auch $L$) : $\operatorname{DSPACE}(\log n)$\\
$\operatorname{NLOGSPACE}$ (auch $NL$) : $\operatorname{NSPACE} (\log n)$\\
$\operatorname{PSPACE} : \bigcup_{k \geq 1} \operatorname{DSPACE}(n^k)$
\end{definition}
\begin{bemerkung}[Typische Probleme in $\operatorname{LOGSPACE}$]
\begin{enumerate}
\item 
Enthällt ein Graph eine bestimmte Konfiguration?
\item
Ist ein ungerichteter Graph zykelfrei?
\item
Addition
\item
Multiplikation(schwieriger)
\item
Ereichbarkeit im ungerichteten Graphen (schwierig, Satz von Reingold)
\end{enumerate}
\end{bemerkung}
\begin{bemerkung}[Typisches Probem in NLOGSPACE]
  Ereichbarkeit in gerichteten Graphen\\
  Raten eines Pfades unter Vergessen bisher besuchter Knoten.
  Mitführen eines Zählers von $1 \ldots n$ Abbruch nach maximal $n$
  Schritten ($n$ = Zahl der Knoten)
\end{bemerkung}
\begin{bemerkung}[Typische Probleme in PSPACE]
Verallgemeinerte Spiele $n \times n$ Schach, Dame etc.\\
Quantifizierte Boolesche Formeln
\end{bemerkung}
\begin{bemerkung}
($2^{\Ocal(\log (n)} = n ^{\Ocal(1)}$)\\
$\operatorname{LOGSPACE} \subseteq \operatorname{NLOGSPACE} \subseteq \Pol \subseteq \operatorname{PSPACE}$\\
$\operatorname{LOGSPACE} \subsetneq \operatorname{PSPACE}$\\
Eine der drei Inklusionen muss echt sein, da $\operatorname{LOGSPACE}$ wegen des 
Platzhierarchiesatzes echt in $\operatorname{PSPACE}$ enthalten ist. \\
Von keiner der drei ist es derzeit bekannt.
\end{bemerkung}
\subsection{Platzkomplexit"at und Nichtdeterminismus}
\begin{satz}[Satz von Savitch]
$s(n)$ platzkonstruierbar $s(n) \geq \log n$\\
$\operatorname{NSPACE}(s(n)) \subseteq \operatorname{DSPACE}(s(n)^2)$
\end{satz}
\begin{beweis}
Sei $L \in \operatorname{NSPACE}(s(n))$ und $T$ eine nichtdeterministische TM. mit $L = L(T)$ und $\operatorname{SPACE}(T(x)) \leq s(n)~~~n = |x|$\\
Sei $V$ die Menge der globalen Konfigurationen von T deren Bänder Größe $s(n)$ haben. Deren Zahl ist durch $2^{ c \cdot s(n)}$ für ein $c$ beschränkt.\\
Beachte: hier geht die Voraussetzung $s(n)\geq\log(n)$ ein, denn der Lesezeiger auf das Eingabeband verbraucht Platz $\log(n)$.\\
Setze $N := 2^{c \cdot s(n)}$  = Anzahl dieser globalen Konfigurationen.\\
Für $g, g' \in V$ schreibe $(g,g') \in E$ falls $g'$ mögliche Ein-Schritt Folgekonfiguration in $T$ ist.\\
Schreibe $s$ für Startkonfiguration von $T$ auf $x$\\
Schreibe $t$ für die akzeptierende Endkonfiguration (oBdA können wir annehmen, dass es genau eine solche gibt)\\
Es gilt dann $x \in L$ \Gdw im Graphen $(V,E)$ ein Pfad von $s$ nach $t$ existiert\\
Definiere rekursive Prozedur $\operatorname{reach}(g,g',i)$ sodass $\operatorname{reach}(g,g',i) = \true$ \Gdw in $(V,E)$ ein Pfad von $g$ nach $g'$ der Länge $\leq 2^i$ existiert.\\
$\operatorname{reach}: V \times V \times \N \to \operatorname{bool}$\\
Es gilt dann:\\
$x \in L \Gdw \operatorname{reach} (s,t,i) = \true$ für $i = c\cdot s(n)$\\
$\operatorname{reach}(g,g', i) = \\
~~~\operatorname{if} (i=0)\\
~~~~~~\operatorname{if} (g = g' \lor (g,g') \in E)\\
~~~~~~~~~\operatorname{return} \true \\
~~~~~~\operatorname{else} \operatorname{return} \false\\
~~~\operatorname{else}:\\
~~~~~\operatorname{for} (g'' \in V)\\
~~~~~~~\operatorname{if}(\operatorname{reach} (g,g'', i-1) \land \operatorname{reach}(g'',g', i-1)) \operatorname{return}: \true\\
~~~~~\operatorname{return}: \false$\\
Ein Stackframe ist größenmäßig durch $\Ocal(s(n))$ beschränkt.\\
Rekursionstiefe = Stackhöhe $\leq c s(n)$\\
Die gesamte Prozedur lässt sich also in Platz $\Ocal (s(n)^2)$ auswerten.\\
Alternativ: funktionale Version von reach:\\
$\operatorname{reach}(g,g',0) = \begin{cases} \true & \operatorname{if} g=g' \operatorname{or} (g,g') \in E\\
\false& \operatorname{sonst}\end{cases}\\
\operatorname{reach} (g,g', i+1) = \operatorname{checkfrom}(g_0, g,g', i)\\
\operatorname{checkfrom}(g'',g,g',i) =\\
~~~\operatorname{reach}(g,g'',i) \land \operatorname{reach}(g'',g',i) \lor \operatorname{checkfrom}(\operatorname{next}(g''), g,g', i)$ Falls $g''$ nicht die letzte Konfiguration ist\\
$\operatorname{checkfrom}(g'',g,g',i) = \operatorname{reach} (g,g'',i) \land \operatorname{reach}(g'', g',i)$ sonst\\
Hierbei sei $g_0, \operatorname{next}(g_0), \operatorname{next}(\operatorname{next}(g_o)), \ldots$ eine beliebige Aufzählung von V.\\Auswerten von $\operatorname{reach}(s,t, c s(n))$ führt auf Ausdrücke der Größe $\Ocal(s(n)^2)$
\end{beweis}
\begin{Korollar}
Ereichbarkeit in Graphen $ \in \operatorname{DSPACE}((\log n)^2)$\\
$\operatorname{NLOGSPACE} \subset \operatorname{DSPACE}(( \log n)^2)$\\
$\underbrace{\operatorname{NSPACE}(n^{\Ocal(1)})}_{= \operatorname{NPSPACE}} = \operatorname{PSPACE}$
\end{Korollar}
\begin{satz}[Immerman-Szelepscényi]
Sei $s(n) \geq \log n$ platzkonstruierbar.\\
$\operatorname{co-NSPACE}(s(n) = \operatorname{NSPACE}(s(n))$\\
Hierbei gilt:\\
$\operatorname{co-NSPACE}(s(n)) = \{L | \strich L \in \operatorname{NSPACE}(s(n))\}$
\end{satz}
\begin{beweis}
Sei $T$ eine $s(n)$ platzbeschränkte NTM für $\Sigma$. Sei $V$ die Menge ihrer globalen Konfigurationen $|V| \leq 2^{c s(n)}$\\
$s$: Startkonfiguration bei Eingabe $x$. $|x| = n$\\
$t$: akzeptierende Endkonfiguration\\
$E = \{ (g,g') | g'$ ist 1-Schritt Folgekonfiguration von $g$\}\\
$x \in L$ \Gdw $t$ ist von $s$ aus in $(V,E)$ \underline{nicht} erreichbar.

%%
%
%%Vorlesung 20.11.2008
%
%%
Folgender nichtdeterministischer Algorithmus \emph{kann} ACCEPT
ausgeben gdw.\ $t$ von $s$ aus \emph{nicht} erreichbar ist, also wenn
$x\notin L(T)$ ist. Ist $x\in L(T)$, so gibt der Algorithmus auf jeden
Fall FAIL aus. Ist aber $x\notin L(T)$, so kann man die
nichtdeterministischen Entscheidungen des Algorithmus so treffen, dass
ACCEPT ausgegeben wird. Bei ungeschickter Wahl dieser Entscheidungen
kann (und wird in den meisten F"allen) trotzdem FAIL ausgegeben.
\begin{verbatim}
/* Invariant: count = # Config reachable from s in <= i steps */
i = 0;count = 1; /* Invariant ok */
while (i <= N) {
      count' = 0; /* count' is to be the new value of count for i+1 */
      for (v:V) { /* for each v we see whether it can be reached from s in
<=i+1 steps.*/
         if (v==s) {count'++;} else {
            c = 0;found = false;
            for (u:V) { /* for each u we check whether v is reachable from
s with last step via u */
                guess path pi of length <=i starting from s;
                if (pi ends in u) {
                    c++;
                    if( (u,v):E ) {found=true; /* found a path of length
<= i+1 from s to v (via u)*/}
                }
            }
            if (found) count'=count'+1;
            else if (c<count)  FAIL; /* We missed some of the u's
reachable in <=i steps */
            else ;
            /* If !found and we haven't FAILed then indeed v isn't
reachable from s in <=i+1 steps so
               we don't need to update count'.*/
        }
     }
     count = count';i++;
}
/* At this point count equals the number of configs reachable from s */
c = 0;found = false;
for (v:V) {
    guess path pi of length <=N starting from s;
    if (pi ends in v) {
       if (v==t) found=true;
       c++;
    }
}
if (c<count || !found) FAIL;
else ACCEPT;
\end{verbatim}
\end{beweis}
\begin{beispiel}
Berechnung von count:\\
In $\leq 3$ Schritten seien 5 Knoten ereichbar\\
in $\leq 4$ Schritten seien 7 Knoten erreichbar\\
Zu Begin der Schleife sei i=3 und count=5\\
\begin{itemize}
\item
Wir können jetzt den Durchlauf der Schleife so steuern,
 dass am Ende des Rumpfes count =7 ist.
\item Egal wie der Durchlauf gesteuert wird, ist am ende count = 7 oder es wurde 
abgebrochen (FAIL)
\end{itemize}
count = 5
\begin{enumerate}
\item 
1. Fall: t nicht erreichbar
Wir können dann T' nach Accept lenken:\\
Rate für jeden ereichbaren Knoten genau den Pfad der ihn erreicht.
\item
2. Fall: t ist erreichbar\\
Egal wie $T'$ gesteuert wird erreichen wir immer FAIL und nich accept.\\
\begin{enumerate}
\item 
Für t wurde der richtige Fall geraten \To FAIL
\item
Für t wurde nicht der richtige Fall geraten \To count > r \To FAIL

\end{enumerate}

\end{enumerate}
\end{beispiel}
\subsection{Ausdruckskraft eines Stacks}
\begin{definition}[s(n)-platzbeschränkte TM mit STACK]
Eine $s(n)$-platzbeschränkte TM mit STACK hat neben einem read only Eingabebande eine feste Zahl von $s(n)$ platzbeschränkte Arbeitsbänder\\
Zusätzlich ein weiteres Arbeitsband S (STACK) welches wie folgt eingeschränkt ist:
\begin{enumerate}
\item 
Wird durch ein Quintupel das Band $S$ verändert, so werden in diesem Schritt alle anderen Bänder nicht verändert.
\item
Wird in einem Quintupel der $S$-Kopf nach rechts bewegt, so wird das aktuelle $S$-Symbol nicht verändert. Im unmittelbar nächsten Schritt wird ein $S$-Symbol beschrieben.
\item
Wird in einem Quintupel der $S$-Kopf nach Links bewegt, so wird das aktuelle $S$-Symbol mit $\square$ überschrieben.
\end{enumerate}
Sei $x$ eine Eingabe. Mit $V$ bezeichnen wir die Menge aller Beschriftungen der Arbeitsbänder außer $S$ und die Positionen der Köpfe auf all diesen Bändern.\\
Für $g,g' \in V$ und $s \in \Sigma$ schreiben wir:\\
$(g,s) \toweil {\operatorname{TOP}} g'$ falls $g$ in $g'$ übergeht bei Lesen von $s$ vom $S$-Kopf\\
$(g,s) \toweil{\operatorname{POP}} g'$ falls $g$ übergeht in $g'$ bei lesen von $s$ beim $S$-Bandes und bewegung des $S$-Kopfes nach links (nach obrigen Regeln)\\
$(g,s) \toweil{\operatorname{PUSH}(s')} g'$ falls $g$ in $g'$ übergeht bei Lesen von $s$ beim $S$-Band und Bewegung des $S$-Kopfes nach rechts mit anschließenden Schreiben von $s'$\\
Es sollte klar sein, wie aus der Maschinenbeschreibung die Relationen $\toweil{\operatorname{TOP}}, \toweil{\operatorname{POP}}, \toweil{\operatorname{PUSH}(s')}$ abgelesen werden können.\\
Eine solche Maschine akzeptiert ein Wort $x$, falls von der Startkonfiguration $g_0(x)$ mit Stack enthällt nur $\$, s_0$die Konfiguration $g_A$ mit Stack $ \$$ ereichbar ist ($s_0, \$$ fest gewählt), wobei
\begin{enumerate}
\item 
$g_0$ die Startbeschriftung zur Eingabe $x$ ist
\item
$g_A$ akzeptierende Endbeschriftung fest gewählt ist (Alle Bänder leer, Lesekopf für die Eingabe am Anfang)
\item
Im Verlauf der Berechnung wird das Feld mit Inhalt $\$ $nie besucht. Erst ganz zum Schluss

\end{enumerate}



\end{definition}
\begin{definition}
$\operatorname{NSPACE}(s(n))+\operatorname{STACK}$ ist die Menge aller Sprachen die von solchen Maschinen erkannt werden.
\end{definition}
\begin{satz}[Satz von Cook]
$s(n) \geq \log n$ platzkonstruierbar\\
$\operatorname{NSPACE}s(n) + \operatorname{STACK} = \operatorname{DTIME}(2^{\Ocal(s(n))})$
\end{satz}
\begin{beweis}
\underline{$\subset$}:\\
Sei T solch eine Maschine und eine Eingabe x vorgegeben.\\
Wir definieren die Relation $M$ wie folgt:\\
$(g,s,g') \in M$ genau dann wenn\\
$g,s \to^\ast g', \$ $\\
und im Verlauf dieser Berechnung wurde $\$$ nicht besucht.\\
Klar. $x \in L(T) \Gdw (g_0(x), s_0, G_A) \in M$\\
Wir werden jetzt die vollständige Wertetabelle von M ausrechnen und dann die Frage durch Nachgucken beantworten.\\
$(g, s,g') \in M$ gilt genau dann, wenn das mithilfe folgender Regeln hergeleitet werden kann.\\
$g,s \toweil {\operatorname{POP}} g' \To (g,s,g') \in M\\
g,s \toweil{\operatorname{TOP}} g', (g',sg'') \in M \TO (g,s,g'') \in M$\\
$g,s \toweil{\operatorname{PUSH}(s')} g',  (g', s', g'') \in M, (g'',s, g'') \in M \To (g,s,g''') \in M$\\
Durch sukzessive Anwendung dieser drei Regeln kann in Zeit $2^{\Ocal(s(n))}$ die Wertetabelle aufgefüllt werden.\\
%%
%
%% Vorlesung 24.11.08
%
%%
\underline{$\supset$}:\\
Sei $T$ eine DTM, die $2^{c\cdot s(n)}$ zeitbeschränkt ist. Definiere folgende Funktionen:\\
$\operatorname{symb}(x,t,p) := (a_1, \ldots a_k)$ sodass $a_i$ steht nach $t$ Schritten von $T$ auf Eingabe $x$
 auf dem $i$-ten Band an Position $p$.\\
$\operatorname{head}(x,t) := (n_1, \ldots , n_k)$ sodass bei Eingabe $x$ steht der Schreib/Lesekopf auf Band $i$ an der Position $n_i$ nach $t$ Schritten\\
$\operatorname{state}(x,t) :=$ Zustand von $T$ bei Eingabe $x$ nach $t$ Schritten\\
Rekursive Definition:\\
$\operatorname{smyb}(x,0,p) = \operatorname{if} 0 \leq p \leq |x|$ then $(x_p, \square, \ldots, \square)$ else $(\square, \ldots , \square)$\\
$\operatorname{head}(x,0) = (0,\ldots, 0)$\\
$\operatorname{state}(x,0) = q_0$\\
$\operatorname{symb}(x,t+1, p) = F(\operatorname{symb}(x,t,p), \operatorname{symb}(x,t,p+1), \operatorname{symb}(x,t, p-1), \operatorname{head}(x,t), \operatorname{state}(x,t))\\
\operatorname{state}(x,t+1) = H(\operatorname{symb}(x,t, \operatorname{head}(x,t)), \operatorname{head}(x,t), \operatorname{state}(x,t))\\
\operatorname{state}(x,t+1) = G( \operatorname{state}(x,t,\operatorname{head}(x,t)), \operatorname{state}(x,t))$\\
Für $F,G,H$ gegeben durch $\delta$\\
$T$ ist $2^{c \cdot s(n)}$ Zeitbeschränkt.\\
\To die Argumente der Fkt. symb, head, state sind durch $\Ocal(s(x))$ beschränkt\\
\To Die Funktionen können daher auf einer (sogar det.) TM mit Stack und Platz $\Ocal(s(n))$ berechnet werden. 
\end{beweis}
\subsection{LOGSPACE-Reduktionen und vollständige Probleme für P und NLOGSPACE}
\begin{definition}[E/A-TM]
Eine (N)TM mit Ein- und Ausgabe ist eine (N)TM mit $k \geq 2$ Bändern, das Band 1 
das Eingabeband (E) ist und Band $k$ das Ausgabeband (A)
\begin{itemize}
\item
$E$ bleibt bei der Berechnung unverändert
\item
$A$ wird nur einmal von links nach rechts beschrieben.
\end{itemize}
Sei $T$ eine E/A-(N)TM und $x \in \Sigma^\ast$. Definiere:\\
$\operatorname{(N)SPACE}_T(x) =$ Platzverbrauch auf den Bändern $2$ bis $k-1$\\
(der sparsamsten Berechnung im Falle von Nichtdeterminismus.)
\end{definition}
\begin{definition}[FSPACE(f(n))]
$g: \Simga^\ast \to \Sigma^\ast \in \operatorname{FSPACE}(f(n)) :\Gdw$\\
es existiert det.\ E/A TM $T$, die $g$ berechnet (bei Eingabe $x$ steht $g(x)$ auf dem Ausgabeband wenn $T$ hält), so dass $\operatorname{SPACE}_T(x) = \Ocal(f(|x|))$\\
$\operatorname{FLOGSPACE} = \operatorname{FSPACE}(\log n)$
\end{definition}
\begin{proposition}
Sind $f,g \in \operatorname{FLOGSPACE}$ so auf $g \circ f$
\end{proposition}
\begin{beweis}
Problem: $g$ braucht $\log(|f(x)|)$ Platz\\Okay da $|f(x) \leq p(|x|)$ Für ein Polynom.\\
(es gibt $2^{\Ocal(\log(|x|))}$ viele Konfigurationen. Daher $2^{\Ocal(\log (|x|)}$ Schritten: halten oder Zyklus.)\\
Aber man kann $f(x)$ nicht zwischenspeichern.\\
Lösung: on-the-fly berechnung von $f(x)$\\
Gegeben E/A TMs $T_G$ udn $T_f$ für $g$ und $f$\
Simuliere die Hintereinanderschaltung von $T_f$ und $T_g$ mit E/A TM T wie folgt:\\
\begin{itemize}
\item
Baue $T_f$ so um, dass das Ausgabeband nur auf einem Feld beschrieben wird. Auf diesem Feld steht das oberste Stacksymbol.
\item
$T$ verhält sich nun wie $T_g$. T liest jedoch nicht vom Eingabeband, sondern vom modifizierten Ausgabeband von $T_f$\\
$T:$\\
Eingabeband:\\
Bänder von $T_f$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$\Ocal(\log(|x|))$\\
Puffer = modifizierte Ausgabeband von $T_f$~~~~$\Ocal(1)$\\
Pufferzähler~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$\Ocal(\log(f(x))) = \Ocal(\log(p(x))) = \Ocal(\log(x))$\\
Bänder von $T_g$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$\Ocal(\log(f(x))) = \Ocal(\log(x))$\\
Ausgabeband

\end{itemize}
Wie simuliert $T$ die Maschine $T_g$:\\
z.B. $T_g$ bewegt Eingabekopf nach rechts:\\
$T$ erhält Pufferzähler um 1\\$T$ berechnet mit dem mod $T_f$ $f(x)$ bis \# Pufferzähler-mal in den Puffer geschrieben wurde\\
T liest vom Puffer und simuliert $T_g$ weiter
\end{beweis}
\begin{definition}[LOGSPACE-Reduktion]
Seien $A,B \subset \Sigma^\ast$\\
$A \leq_L B :\Gdw \exists f \in \operatorname{FLOGSPACE}$ mit ($x \in A \Gdw f(x) \in B)$

\end{definition}
\begin{proposition}
$\forall A,B \subset \Sigma^\ast$ gilt:
\begin{enumerate}
\item 
$A \leq_L A$ (Reflexivität)
\item
$A \leq_L B$ und $B\leq_LC$ dann $A \leq_L C$ (Transitivität
\end{enumerate}
\end{proposition}
\begin{beweis}
\begin{enumerate}
\item 
ist klar
\item
Folgt aus vorherigem Satz

\end{enumerate}

\end{beweis}
\begin{definition}[NLOGSPACE-vollständig]
$A \subset \Sigma^\ast$ ist vollständig für NLOGSPACE falls
\begin{enumerate}
\item 
$A \in \operatorname{NLOGSPACE}$
\item
$B \leq_L A$ für alle $B \in \operatorname{NLOGSPACE}$
\end{enumerate}
\end{definition}
\begin{definition}[P-vollständig]
$A \subset \Sigma^\ast$ ist vollständig für P falls
\begin{enumerate}
\item 
$A \in \operatorname{P}$
\item
$B \leq_L A$ für alle $B \in \operatorname{P}$
\end{enumerate}
\end{definition}
\begin{definition}[REACH]
Gegeben: Gerichteter Graph $G = (V,E), s,t \in V$\\
Frage: Gibt es einen Pfad von $s$ nach $t$ in G?
\end{definition}
\begin{bemerkung}
$\operatorname{UREACH} \in \operatorname{LOGSPACE}$ Rechte-Hand-Regel.
\end{bemerkung}
\begin{satz}
$\operatorname{REACH}$ ist $\operatorname{NLOGSPACE}$-vollständig
\end{satz}
\begin{beweis}
\begin{enumerate}
\item 
$\operatorname{REACH} \in \operatorname{NLOGSPACE}$:\\
Speichere folgendes:\\
Einen akt. Knoten $v \in V$\\
einen Zählen\\[.2cm]
Starte mit $v=s$ und $n=0$\\
Rate Nachfolger $v'$ von $v$ mit $(v,v') \in E$\\
etze $v:= v'$ und $n= n+1$\\
Akzeptiere falls $v= t$ erwerfe falls $n = |V|$\\
\item
Sei $A \in \operatorname{NLOGSPACE}$\\
\To es existiert NTM $T$ mit $L(T) = A$ und $\operatorname{NSPACE}_T(x) = c \cdot \log(|x|)$\\
OBdA hat $T$ nur eine globale Endkonfiguration $E$
T besitzt bei Eingabe $x$ $2^{\Ocal(\log(|x|))} = \Ocal(p|x|))$ viele globale Konfigurationen.\\
Betrachte $G_x = (V,E)$ mit $V$ = Globale Konfigurationen von $T$ bei eingabe $x$\\
$E = \{(k,k') | T$ kommt in einem Schritt von $k$ nach $k'$\}\\
Jetzt gilt:\\
$x \in A \Gdw (G_x,S,E) \in \operatorname{REACH}$\\
$G_x$ kann aber aus $x$ in $\operatorname{LOGSPACE}$ berechnet werden: zähle systematisch alle Paar von $(k,k')$ von Konfigurationen auf und Prüfe ob $k \to_1 k'$
\end{enumerate}

\end{beweis}
\begin{definition}[HORN-SAT]
Gegeben: KNF $F$ mit maximal einem positiven Literal pro Klausel. (oBdA: 3 literale)\\
Frage: Ist $F$ erfüllbar?
\end{definition}
\begin{satz}
$\operatorname{HORN-SAT}$ ist vollständig für $\Pol$
\end{satz}
%%
%%%
%% Vorlesung 01.12.2008
%%%
%%

\begin{beweis}
Sei eine polynomialzeitbeschränkte DTM M vorgegeben und Eingabe $x \in \Simga^\ast$\\
Wir konstruieren eine Menge HORN Formeln $\Hcal$ , sodass $\Hcal$ unerfüllbar ist \Gdw $M$ die Eingabe $x$ akzeptiert.\\
\underline{Variablen:}\\
$\operatorname{Band}(i,t,a) =$ für $i \leq T , t \leq T, a \in \Sigma, T = $ max Laufzeit von $M$ auf $x$ (polynomiell beschränkt in $|x|$)\\
$\operatorname{Kopf}(i,t)$ für $i,t \leq T$\\
$\operatorname{Zustand}(t,q)$ für $t \leq T q \in Q_M$\\
$X(i,t,b,q',d)$ für $i,t\leq T$, $b \in \Sigma, q' \in Q_m, d \in \{-1,0,1\}$
\underline{Klauseln:}\\
$\to \operatorname{Kopf}(0,0)$ /* Am Anfang steht der Kopf an Pos. O\\
$\to \operatorname{Zustand}(0,q_0)$\\
$\to \operatorname{Band}(i,0,x_i)$ für $i = 0,\ldots, |x|-1, x = x_0x_1\ldots$
$\to \operatorname{Band}(i,0,\square)$ für $i \geq |x|$\\
falls $\delta(a,q)=(b,q',d)~~~d \in \{-1,0,1\}$:\\
$\operatorname{Kopf}(i,t), \operatorname{Band}(i,t,a), \operatorname{Zustand}(t,q) \to X(i,t,b,q',d)$\\
$X(i,t,b,q',d) \to \operatorname{Zustand}(t+1,q')$\\
$X(i,t,b,q',d) \to \operatorname{Band}(i,t+1,b)$\\
$X(i,t,b,q',d) \to \operatorname{Kopf}(i+d, t+1)$\\
$\operatorname{Zust}(T,q_x) \to \false$\\
$\operatorname{Kopf}(i,t), \operatorname{Band}(j,t,a) \to \operatorname{Band}(j,t+1,a)$ für $i,j,t \leq T, i \ne j, a \in \Sigma$\\
Bemerkung: $\false$ ist genau dann herleitbar, wenn $M$ auf $|x|$ akzeptiert.\\
Beobachtung: die obige Klauselmenge kann aus M und x in LOGSPACE berechnet werden.

\end{beweis}
\begin{bemerkung}[Erinnerung]
$\operatorname{PSPACE}= \operatorname{DSAPCE}(n^{\Ocal(1)}) = \operatorname{NSPACE}(n^{\Ocal(1)})$ (wegen Satz von Savitch)\\
$\operatorname{NSPACE}(n^2)$ ist wahrscheinlich nicht in $\operatorname{DSPACE}(n^2)$ enthalten aber sehr wohl in $\operatorname{DSPACE}(n^4)$
\end{bemerkung}
\begin{definition}[Quantifizierte Boolesche Formeln]
Quantifizierte Boolesche Formeln sind  durch folgende Gramatik gegeben:\
$\varphi, \psi ::== X | \varphi \land \psi | \varphi \lor \psi | \neg \varphi | \forall X.\varphi | \exists X.\varphi$\\
Eine QBF ist geschlossen, wenn sie keine freien Variablen enthällt.\\(alle vorkommenden Variablen sind durch $\forall$ oder $\exists$ gebunden)\\
Das Problem $\operatorname{QBF}$ besteht darin, zu gegebener geschlossener QBF $\vieh$ den Wahrheitswert zu bestimmen.
\end{definition}
\begin{bemerkung}
$\operatorname{SAT}$ und $\operatorname{TAUT}$ sind Speziallfälle von $\operatorname{QBF}$
\end{bemerkung}
\begin{definition}[Formale Semantik von QBF]
Sei $\eta$ eine Belegung der Variablen.\\
Wie definieren rekursiv:\\
$\eta \models \varphi~~~ (\varphi \operatorname{QBF}$\\
$\eta \models X \Gdw \eta(X) = \true$\\
$\eta \models \varphi \land \psi \Gdw \eta \models \varphi$ und $\eta \models \psi$\\
$\eta \models \varphi \lor \psi \Gdw \eta \models \varphi$ oder $\eta \models \psi$\\
$\eta \models \neq \varphi \Gdw \eta \not \models \varphi$\\
$\eta \models \forall X. \psi \Gdw \eta[X\mapsto \true] \models \psi$ und $\eta[X \mapsto \false] \models \psi\\
\eta \models \exists X. \psi \Gdw \eta[X \mapsto \true] \models \psi$ oder $\eta[X \mapsto \false] \models \psi$
\end{definition}
\begin{satz}
$\operatorname{QBF} \in \operatorname{PSPACE}$
\end{satz}
\begin{beweis}
Die Klauseln rekursiv ausprogrammieren. Rekursionstiefe, sowie Stackframes haben lineare Größe
\end{beweis}
\begin{satz}
$\operatorname{GBF}$ ist $\operatorname{PSACE}$ vollständig
\end{satz}
\begin{beweis}
Sei $M$ polynomiell platzbeschränkte TM, Eingabe $x$ vorgegeben.\\
$V =$ Menge der globalen Konfigurationen\\
$E = \{(v,v') | v,v' \in V, v'$ Ein-Schritt-Nachfolger von $v\}$\\
$s$ Startkonfiguration, $t$ akzeptierende Endkonfiguration\\
$x \in L_M \Gdw (s,t) \in E^\ast$\\
\underline{Erinnerung:}\\
$x \in L_m \Gdw \operatorname{REACH}(s,t, T)~~T$ sodass $2^T > |V|$\\
$\operatorname{REACH}(u,v,0) \Gdw (u,v) \in E$ oder $u=v$\\
$\operatorname{REACH}(e,v,t+1) \Gdw \exists w. \operatorname{REACH}(u,w,t) \land \operatorname{REACH}(w,r,t)$\\
Codiere globale Konfiguration durch boolesche Variablen ($T$ Stück)\\
Definiere für $i= 0, \ldots T$ QBF Formel:\\
$\varphi_i(u,v)$ in $2T$ Variablen, sodass $\varphi_i(u,v) \Gdw \operatorname{REACH}(u,v,i)$\\
$\varphi_0(u,v) :\Gdw u=v$ oder $(u,v) \in E$\\
$\varphi_i+1(u,v) :\Gdw \exists w. \varphi_i(u,w) \land \varphi_i(w,v)$~~~~~~~$(\ast)$\
gib aus $\varphi_T(i,t)$\\
Dies ist noch keine Polynomielle Reduktion da $|\varphi_i(u,v)| = \Omega(2^i)$\\
Ersetze $(\ast)$ durch:\\
$\exists w . \forall y,t (y = u \land z= w \to \varphi_i(y,z) )\land (y = w \land z = v \to \varphi_i(y,z)$\\
Besser noch:\\
$\exists w \forall y,z: (( y=u \land z=w) \lor(y=w \land z=v)) \To \varphi_i(y,z)$

\begin{tabular}{ccc}
&$\operatorname{EXP}$\\
&$\operatorname{PSPACE}$\\
&$\operatorname{PH}$\\
&$\vdots$\\
$\Sigma_2^P$&  &$\Pi_2^P$\\
$\operatorname{NP}$&&$\operatorname{co-NP}$\\
&$P$\\
&$NL$\\
&$L$
\end{tabular}
\end{beweis}
\begin{bemerkung}
Ermittlung von Gewinnposition in Spielen, deren Positiongröße und Spieldauer polynomiell beschränkt ist, ist in PSPACE, denn man kann das Problem in QBF formulieren\\
Oft sind solche Spiele auch PSPACE vollständig
\end{bemerkung}

%%
%%%
%% Vorlesung 4.12.2008
%%%
%%
\newpage
\section{Programmiersprachen und Komplexität}

\subsection{Beschränkte Notationsrekursion, Satz von Cobham (1965)}
\begin{definition}[Notationsrekursion]
Sei $g$ eine $n$-Stellige Funktion auf $\N$ und $h$ eine $n+2$-Stellige Funktion\\
Aus $g$ und $h$ wird die $n+1$-stellige Funktion $f$ durch Notationsrekursion definiert, wenn gilt:\\
$f(0, \vec x) = g(\vec x)\\
f(x, \vec x) = h(x, f( \frac x 2, \vec x)$ falls $x >0$\\
Man schreibt: $f = \operatorname{rec}(g,h)$ 
\end{definition}
\begin{definition}[Grundfunktionen]
\begin{enumerate}
\item 
'Nachfolger': $S_0(x) = 2x ~~~ S_1(x) = 2x+1$
\item
'Vorgänger': $p(x) = \frac x 2$
\item
'Null' : 0
\item
'Fallunterscheidung' : $\operatorname{coud}(x,y,z,w) = \begin{cases} y & \text{falls} x = 0\\
z & \text{falls } x \text{ gerade und } > 0\\
w & \text{falls } x \text{ ungerade} \end{cases}$
\item
'Projektion': $\operatorname{proj}^n_i(\vec x) = x_i$ 
\end{enumerate}
\end{definition}
\begin{bemerkung}
Rekursionstiefe einer durch Notationsrekusion definierten Funktion $f = \operatorname{rec}(g,h)$\\
$f(x, \vec x)$ ist $\log x \approx |x|$\\
Hier: $|x|$ = Länge der Binärdarstellung von $x = \lceil \log_2 (x+1) \rceil$\\
$S_1(\underbrace{1101_2}_{=13_{10}}) = \underbrace{1101}_{= 27_{10}}$\\
$S_0 (1101) = 11010\\
p(11011) = 1101\\
p(1101101) = 110110\\
\operatorname{concat}(x,y) = x 2^{|y|} + y\\
\operatorname{concat}(x,0) = x\\
\operatorname{concat}(x, S_0(y)) = S_0(\operatorname{concat}(x,y))$ Falls $y > 0\\
\operatorname{concat}(x, S_1(y)) = S_1(\operatorname{concat}(x,y))$\\
Formal:\\
$\operatorname{concat'} = rec (g,h)$ wobei:\\
$g(x) = x$\\
$h(y,z,x) = \operatorname{cond}(y,0,  S_0(z), S_1(z))$\\
$\operatorname{concat}(x,y) = \operatorname{concat'}(y,x)$
\end{bemerkung}
\begin{satz}
Die Klasse der Funktionen, die aus den Grundfunktionen mit Notationsrekursion und Komposition gebildet werden kann, ist gleich 
der Klasse der primitiv rekursiven Funktionen
\end{satz}
\begin{beweis}
Definiere:\\
$\operatorname{code}(x) = 2^{x}$\\
$\operatorname{decode}(x) = |x|$\\
Ist $f(\vec x)$ primitiv rekursiv, so gibt es eine Funktion $f^\#$ die mit Notationsrekursion definierbar ist, sodass gilt:\\
$\operatorname{decode}\left(f^\#(\operatorname{code}(x_1), \ldots, \operatorname{code}(x_n))\right) = f(x_1, \ldots x_n)$\\
Decode und code sind ebenfalls definierbar und daraus erhält man Def.\ von $f$\\
Intuittion:\\
$f(0) = 1$\\
$f(x ) = \operatorname{concat}(f(\frac x 2 ) , f(\frac x 2 ))$\\
$|f(0)| = 1\\
|f(x)| = 2 |f(\frac x 2)|\\
|f(x)| = 2^{|x|}$ 
\end{beweis}
\begin{definition}[beschränkte Notationsrekursion (Cobham)]
$g$: $n$-stellig, $h: n+2$ Stellig, $k: n+1$ Stellig\\
$f = \operatorname{brec}(g,h,k)$ (f entsteht aus g,h, k durch \underline{beschränkte} Notationsrekursion) wenn gilt:\\
$f(0,\vec x ) = g(\vec x)$\\
$f(x,\vec x) = h(x, f( \frac x 2 , \vec x), \vec x)$\\
$f( x, \vec x) \leq k(x, \vec x)$\\
\end{definition}
\begin{bemerkung}
$\operatorname{brec}(g,h,k)$ ist nur wohlgeformt, falls die dritte Formel gilt\\
\end{bemerkung}
\begin{bemerkung}[Alternative Definition]
$f(0,\vec x) = g(\vec x)$\\
$f(x,\vec x) = \min( k(x, \vec x), h(x, f(\frac x 2, \vec x), \vec x))$
\end{bemerkung}
\begin{definition}
$x \# y = 2^{|x| \cdot |y|}$\\
es gilt: $|x \# y | = |x| \cdot |y|$\\
\end{definition}
\begin{satz}[Cobham]
Die Klasse der Funktionen, die mit den Grundfunktionen $0, S_0,S_1, p, \operatorname{cond}, \operatorname{proj}, \#$ durch beschränkte Notationsrekursion und Komposition definierbar sind ist gleich $\operatorname{FP}$ (Polynomielle Zeit)\\
Also $\operatorname{brec} = \operatorname{FP}$
\end{satz}
\begin{beweis}
\underline{$\operatorname{brec} \subset \operatorname{FP}$} Durch Induktion über Darstellung.\\
Grundfunktionen $\in \operatorname{FP}$\\
Komposition, da $\operatorname{FP}$ unter Komposition abgeschlossen ist.\\
$\operatorname{brec}$:\\
ind $g,h, k \in \operatorname{FP}$ so auch $\operatorname{brec}(g,h,k)$ falls wohlgeformt:\\
Rekursionstiefe für $f(x, \vec x)$ ist $|x|$\\
Größe der Zwischenergebnisse ist beschränkt durch $|k(x,\vec x)$ (oBdA $k$ monoton)\\[.2cm]
\underline{$\operatorname{FP} \subset \operatorname{brec}$} Mithilfe von $\#$ als Schranke lässt sich concat definieren.\\
$|\operatorname{concat} \left(x,y\right) | = |x| + |y|  \leq \left( |x|+1\right) \left(|y|+1\right) = | S_0(x) \# S_1(y)| $\\
Es gilt sogar $\operatorname{concat}\left(x,y\right) \leq S_1\left(x\right) \# S_1(\left(x\right)$\\
Mit $\operatorname{concat}$ und $\#$ erhällt für jedes Polynom p eine Funktion, sodass\\
$f\left(|x|\right) = | f_p\left(x\right)|$\\
Ein Schritt Funktion einer $TM$ kann somit mit brec und $f_p$ polynomiell lang iteriert werden.
\end{beweis}
\begin{bemerkung}[Beschränkte Arithmetik]
Grundfunktionen $S_0, S_1, \operatorname{cond}, \#, \ldots$\\
Notationsinduktion:\\
$\varphi(0) \land \left(\forall x. \varphi\left(\frac x 2\right) \to \varphi(x)\right) \to \forall x. \varphi(x)$\\
Für Formeln der Form:\\
$\varphi(x) = \exists y \leq t. \psi(x,y)$\\
in $\psi(x,y)$ sind alle Quantoren der Form:\\
$\exists z \leq |t| ~~~~~~\forall z \leq |t|$
\end{bemerkung}
\begin{satz}[Buss]
Ist $\forall x.\exists y.\psi(x,y)$ beweisbar, so gibt es $\operatorname{FP}$ Funktion, die zu jedem $x$ ein passendes $y$ findet.
\end{satz}
\subsection{Sichere Rekursion nach Bellantoni-Cook}
1992 stellen Bellantoni, Cook eine Variante von Cobhams System vor, die ohne explizite Schranken auskommt.
\begin{definition} 
Die Variablen einer Funktion werden in 'sicher' und 'normal' eingeteilt.\\
Je mehr Variablen sicher sind, umso besser.\\
Das System BC (Belantoni Cook) besteht aus allen Funktionen die mit den folgenden Regeln definiert werden können:\\
\underline{Notation}: $f(\vec x; \vec y)$ bedeutet: die $\vec x$ sind normal, die $\vec y$ sind sicher.
\begin{itemize}
\item Grundfunktionen: $0, S_0(;x), S_1(;x), p(;x), \operatorname{cond}(;x,y,z,w)$\\
Alle Argumente der Grundfunktionen sind sicher. 
\item Projektionen: $\operatorname{proj}(\vec x;\vec y)=x_i,  \operatorname{proj}(\vec x;\vec y)=y_i$  
\item
Komposition:\\
$f\left(\vec x; \vec y\right) = g\left( u_1 \left(\vec x;\right), \ldots , u_m\left(\vec x;\right); v_1 \left(\vec x; \vec y\right), \ldots , v_n(\vec x; \vec y)\right)$\\
Falls $y, \vec u, \vec v \in \operatorname{BC}$ so auch $f$\\Will man eine Funktion in 
eine normale Argumentationsposition einsetzen, so müssen all ihre Argumente vorher auf normal herabgestuft werden 
(Formal durch Komposition mit einer Projektion)
\item
Sichere Notationsrekursion:\\
$f\left(x, \vec x; \vec y\right) = \begin{cases}
g(\vec x; \vec y) & \text{falls } x = 0\\

h(x,  \vec x; f\left(\frac x 2, \vec x, \vec y\right) & \text{falls } x > 0
\end{cases}$

Sind $g,h,$ aus $\operatorname{BC}$ so auch $f$\\
Rekurriert wird nur über normale Argumente.\\
Zugriff auf Ergebnisse rekursiver Aufrufe kann nur über sichere Argumente erfolgen.
\end{itemize}
Man schreibt: $f = \operatorname{srec}(g,h)$
\end{definition}
\begin{beispiel}
$\operatorname{concat}(y,x) = x \cdot 2^{|y|} + y $\\
$\operatorname{concat}(0,x) = x\\
\operatorname{concat}(y,x) = \operatorname{cond}\left(y, S_0\left(\operatorname{concat}\left(\frac y 2, x\right) \right), S_1\left(\operatorname{concat'}\left(\frac y 2 ,x\right)\right)\right)$\\Da über $y$ rekurriert wird muss y als normal eingestuft werden.\\x kann als sicher eingestuft werden.\\
Verwendung der rekursiven Aufrufe erfolgt über sichere Positionen.\\
Formal:\\
$g(;x) = x$\\
$h(y; z,x) = \operatorname{cond}\left(;y,0, S_0\left(;z\right), S_1\left(;z\right)\right)$\\
Formal ist h eine sichere Komposition aus $\operatorname{cond}(;u,v,w,z)$ und $\operatorname{proj}(y;z,x) = y$ und 
 $O( y; z,x)= 0$ und $ w(y; z,x) = S_0(z)$ und  $v(y; z,x) = S_1(;z)$.\\
\\
$\operatorname{concat} = \operatorname{srec}(g,h)$\\[.2cm]
Ist das folgende legal in BC?:\\
$f(0;) = S_1(;0)$\\
$f(x;) = \operatorname{concat}(f(x/2;);f(x/2;))$
\\\\
Hier w"are: 
$h(x;z) = \operatorname{concat}(z;z)$\\
$h(x;z) =$ Komposition von $\operatorname{concat}(u; v)$ mit \\
$u(x;z) = z$ und $v(x;z) = z$ ist nicht legal, da sichere Variable in normale Position u eingesetzt wurde.\\[.2cm]
\\
Folgende Definition ist aber legal:\\

$f(0,y;) = y\\
f(x,y;) = \operatorname{concat}(y; f(x/2,y;$\\
Was ist $|f(x,y;)|$ als Funktion von $|x|$ und $|y|$?
\end{beispiel}
\end{document}
