\section{Komplexitätsklassen und das $P$-$NP$-Problem}
\inhalta{9-15}
\only<article>{\begin{frame}
Im vierten Kapitel haben wir über den Begriff der Berechenbarkeit gesprochen. 
Dabei ging es um die prinzipielle Lösbarkeit von Berechnungsproblemen. 
Jetzt wollen wir unser Augenmerk auf den Berechnungsaufwand von Algorithmen richten. 
Für das praktische Lösen von Berechnungsproblemen ist es nämlich nicht genug, 
einen Algorithmus zu haben, der das Problem löst. Um von praktischem Interesse zu sein, 
darf dieser Algorithmus nicht zu viele Ressourcen benötigen. 
Die beiden wichtigsten Ressourcen, in denen man die Berechnungskomplexität misst, 
sind Rechenzeit und Speicherplatz. 
Für die praktische Lösung eines Berechnungsproblems wird man im Allgemeinen 
nach einem möglichst effizienten Algorithmus suchen. 
Hat man für ein Berechnungsproblem einen Algorithmus gefunden 
und seinen Bedarf an Rechenzeit und Speicherplatz abgeschätzt, 
so hat man zumindest schon mal eine obere Schranke für die Komplexität des Berechnungsproblems. 
Falls es einen noch effizienteren Algorithmus gibt, würde man den natürlich auch gerne haben. 
Für eine vollständige Analyse der Berechnungskomplexität eines Berechnungsproblems 
ist es daher auch von Interesse, eine untere Schranke für seine Berechnungskomplexität zu bestimmen. 
Das Bestimmen einer unteren Schranke ist oft schwierig, 
da diese untere Schranke ja für alle Algorithmen gelten muss, die das Problem lösen. 

Wir werden uns in der folgenden kurzen Einführung  in die Komplexitätstheorie 
auf den Zeitaufwand von Algorithmen 
und auf die Zeitkomplexität von Berechnungsproblemen konzentrieren.
Dies sollte aber nicht darüber hinwegtäuschen, dass auch der Speicherplatzbedarf 
( \glqq Bandkomplexität \grqq ) ein wichtiges Kriterium für die Effizienz von 
Algorithmen und die Komplexität von Problemen ist. 
Oft gibt es bei Problemen auch einen trade-off  zwischen Zeitbedarf und Speicherplatzbedarf 
von Algorithmen, die das Problem lösen, d.h. es gibt einerseits Algorithmen, 
die das Problem schnell, aber mit hohem Speicherplatzbedarf lösen und andererseits 
Algorithmen, die viele Rechenschritte benötigen, aber nur wenig Speicherplatz.
\end{frame}}

\only<presentation>{\begin{frame}

Neues Ziel: \pause \Fb{Aufwand der Lösung von Problemen untersuchen} \pause 

wichtigste Ressourcen:  \pause  \Fb{Rechenzeit und Speicherplatz der Lösungsalgorithmen} \pause 

obere Schranken für ein Problem: \pause 
\begin{itemize}
\item  Untersuche {\em einen} Lösungsalgorithmus  \pause und
\item  schätze Bedarf an Rechenzeit und Speicherplatz ab 
\end{itemize}
\pause untere Schranken für ein Problem:  \pause 
\begin{itemize}
\item Gültig für {\em alle} Lösungsalgorithmen,  \pause 
\item i.d.R. sehr schwer
\end{itemize}

 \pause Hier nur:  Zeitkomplexität von Berechnungsproblemen \pause 

Oft \Fb{trade-off}  zwischen Zeitbedarf und Speicherplatzbedarf bei Problemen: \pause 
\begin{itemize}
\item  schnelle Algorithmen  mit hohem Speicherplatzbedarf  \pause oder
\item 
langsame Algorithmen auf wenig Speicherplatz.
\end{itemize}
 \end{frame}}



\only<article>{\begin{frame}

Wie misst man den Zeitbedarf eines Algorithmus? 
Für die Praxis kommt es natürlich auf den tatsächlichen Zeitbedarf, 
z.B. in Sekunden, an. Da dieser Zeitbedarf aber stark von der verwendeten Hardware abhängt 
und die Hardware sich ständig weiterentwickelt, 
macht eine derartige Angabe bei einer theoretischen Untersuchung wenig Sinn. 
Stattdessen sollte man ein theoretisches Computermodell betrachten, 
dass in der Praxis existierende Computer hinreichend gut modelliert, 
so dass Komplexitätsaussagen in diesem Modell sich auch auf 
in der Praxis existierende Computer übertragen lassen. 
Das zu diesem Zweck meistbenutzte Modell ist das Mehrband-Turingmaschinenmodell. 
Wir wollen uns auf Turingmaschinen beschränken, 
die bei jeder Eingabe nach endlich vielen Schritten aufhören zu rechnen. 
Berechnungsprobleme kann man meistens durch eine zu berechnende Wortfunktion 
beschreiben oder als Wortproblem für eine geeignete Sprache auffassen.
\end{frame}}




\begin{frame}

\begin{definition} \pause 
 Für eine deterministische Mehrband-Turingmaschine $M$
sei 
\[time_{M}(w) = \textrm{ Schrittzahl von }M\textrm{  bei Eingabe von }w\] 
(Schrittzahl: Zahl Übergänge von Startkonf. bis Berechnungsende)
 \pause

Sei $f:\nz\rightarrow\nz$ eine totale Zahlenfunktion.  \pause 
\begin{itemize}
\item Die Klasse $FTIME(f)$ besteht  aus allen totalen Wortfunktionen $g:E^*\rightarrow E^*$
 \pause (über irgendeinem Alphabet $E$), \pause 
für die es eine deterministische Mehrband-Turingmaschine $M $
mit Eingabealphabet $E $
gibt,  \pause die die Funktion $g $
berechnet  \pause und bei Eingabe eines Wortes $w $
nach höchstens $f(|w|)$ Schritten anhält,  \pause 
d.h. $time_{M}(w) \leq f(|w|)$  \pause für alle Eingaben 
$w $
erfüllt. \pause 


\item Die Klasse $TIME(f)$  \pause besteht  aus allen Sprachen 
 $L$ (über irgendeinem Alphabet $E$), \pause 
für die es eine deterministische Mehrband-Turingmaschine $M$
  mit Eingabealphabet $E $ gibt,  \pause die $L(M) = L$  \pause 
und  $time_{M}(w) \leq f(|w|)$ für alle Eingaben $w$
 erfüllt. 


\end{itemize}
\end{definition}

\end{frame}


\begin{frame}

\begin{remark}

 \only<article>{(1) Wir messen den Zeitbedarf hier nur in Abhängigkeit 
von der Länge $|w|$ des jeweiligen 
Eingabewortes $w$. Man könnte den Zeitbedarf noch genauer in 
Abhängigkeit direkt von dem jeweiligen Eingabewort $w $
messen. Für die meisten Untersuchungen reicht unsere Definition aber aus.

 (2) Wir verwenden Mehrbandmaschinen, da sie etwas realistischere Zeitkomplexitäten 
 liefern als Einbandmaschinen. 
 Bei Einbandmaschinen kann man z.B.  Zwischenergebnisse nur auf einem noch nicht benutzten 
 Teil des Bandes ablegen und muss für das Hin-und-Herlaufen des Lese-Schreibkopfes viel Zeit verwenden, 
 während dies in der Praxis nicht der Fall ist. 
 Es sei daran erinnert, dass man Mehrbandmaschinen durch Einbandmaschinen simulieren kann (Satz \ref{Mehrbandmaschine}). 
 Eine Analyse des Beweises zeigt, dass jede Mehrbandmaschine, die in Zeit $O(f(n))$ arbeitet, 
 durch eine Einbandmaschine simuliert werden kann, die in Zeit $O(f^2(n))$ arbeitet. 

 (3) Die verwendeten Maschinen $M$ müssen in allen Fällen anhalten. Bei $w\not\in M$
darf es also keine Endlosschleifen geben, d.h. $M$ muß hier in einem 
Nichtendzustand steckenbleiben.
}
 \only<presentation>{
(1) Zeitbedarf wird in Abhängigkeit von $|w|$ gemessen  \pause \\[1ex]

 (2) Mehrbandmaschinen liefern realistischere Zeitkomplexitäten als Einbandmaschinen.  \pause \\[1ex]

 Jedoch: Arbeitet Mehrbandmaschine in Zeit $O(f(n))$,  \pause so gibt es äquivalente
  Einbandmaschine in Zeit $O(f^2(n))$ \pause  \\[1ex]

 (3) $M$ muß in allen Fällen anhalten.  \pause \\[1ex]
Bei $w\not\in L(M)$ also keine Endlosschleifen möglich,   \pause \\d.h. $M$ muß dann in einem 
Nichtendzustand steckenbleiben.
}

\end{remark}
\end{frame}





\begin{frame}\begin{cont}{}

\only<article>{ (4) Oft werden Zahlenfunktionen $h:\nz\rightarrow\nz$
 berechnet. Man betrachtet dann im Allgemeinen die korrespondierende Wortfunktion 
 $g:E^*\rightarrow  E^*$, die für jede Zahl $n$ das Wort $bin(n)$ auf $bin(h(n))$ abbildet 
(und Binärwörter, die keine natürliche Zahl darstellen, z.B. auf das leere Wort abbildet), 
und untersucht deren Komplexität.

(5) Dieses Komplexitätsmaß heißt Bitkomplexität. Die Bezeichnung rührt
daher, dass jeder einzelne Konfigurationsübergang gezählt wird. Ein
Konfigurationsübergang beinhaltet nämlich eine Änderung die sich durch
konstant viele Bits beschreiben lässt. Ein anderer Name dafür ist
logarithmisches Kostenmaß. Der Grund für diese Bezeichnung wird beim Vergleich
mit dem nachfolgend eingeführten uniformen Kostenmaß klar.

(6) Neben dieser  Bitkomplexität 
findet man in der Literatur aber auch die so genannte uniforme Komplexität. 
Dabei zählt man nur die Zahl der `elementaren' Rechenoperationen, 
die nötig sind, um aus $n $ den Wert $f(n)$ zu berechnen. 
Die uniforme Komplexität ist aber nicht immer angemessen. 
Zum Beispiel kann man die Zahl $2^{2^n}$ berechnen, indem mit $x:= 2$ startet und 
dann $n$-mal die Operation $x:= x^2$ durchführt. Es reichen also $n$ Multiplikationen. 
Aber allein zum Hinschreiben des Ergebnisses, der Zahl   $2^{2^n}$, in Binärschreibweise,
braucht man $2^n$ Schritte. 
Die uniforme Komplexität ist hier unangemessen, da die Elementaroperationen 
hier auf sehr gro"se Zahlen angewendet werden. 
In der Praxis kann man aber wie im Turingmaschinenmodell letzten Endes 
pro Zeiteinheit nur eine Bitoperation durchführen. Das führt dazu, dass bei
der Umrechnung vom uniformen Kostenmaß in die Bitkomplexität ein Faktor
proportional zur Operandengröße auftritt (Bsp.: Um zwei $N$-Bit-Zahlen zu
addieren, benötigt man eine Anzahl von Bitoperationen, die proportional zu $N$
ist.)
}
 \only<presentation>{
(4) Komplexität von  Zahlenfunktionen $h:\nz\rightarrow\nz$ \pause \\
 über  korrespondierende Wortfunktion 
 $g:E^*\rightarrow  E^*$,  \pause \\die für jede Zahl $n$ das Wort $bin(n)$ auf $bin(h(n))$ abbildet 
 \pause \\[1ex]
(5) Bezeichnung: \Fb{Bitkomplexität}: jeder Übergang ändert
Konfiguration der TM `um konstant viele Bits'
 \pause \\[1ex]
(6) Alternativ: \Fb{uniforme Komplexität} \pause 
 \\[1ex]
hier: Zählung der `elementaren' Rechenoperationen, \\
die nötig sind, um $f(n)$ aus $n $  zu berechnen. \pause  
 \\[1ex]

Beispiel: Berechne Zahl $2^{2^n}$ wie folgt:  \pause \\[1ex]
Starte mit $x:= 2$  \pause und führe $n$-fach  $x:= x^2$ aus \pause 

\begin{itemize}\item 
Uniforme Komplexität: $n$ \pause 
\item
Bit-Komplexität mindestens $2^n$,  \pause da $2^{2^n}$ bereits Länge $2^n$ hat! \pause 
\item 
Uniforme Komplexität nicht immer angemessen.  \pause 
\item
Turingmaschinenmodell / Bitkomplexität i.d.R. passender! 
\end{itemize}
}
\end{cont}
\end{frame}


\only<article>{\begin{frame}

Es stellt sich die Frage, welche Komplexitätsklassen für die Praxis von Interesse sind. 

Einerseits sind Algorithmen, die exponentiell viel Zeit verbrauchen, 
d.h. bei einer Eingabe der Länge $n $ z.B. $2^n $
Zeiteinheiten benötigen, sicher uninteressant. 

Zu verlangen, dass ein Algorithmus bei Eingabe der Länge $n $
nur $O(n)$ Schritte benötigt, scheint wiederum etwas zu streng zu sein. 
Realistisch, zumindest bei nicht zu gro"sen Eingaben, sind auch Algorithmen, 
die in Polynomzeit arbeiten, mit einem Polynom nicht zu hohen Grades. 
Da die Klasse aller Polynome  sehr gute theoretische Eigenschaften hat, 
werden wir uns im Folgenden auf Probleme konzentrieren, die in Polynomzeit gelöst werden können.

\end{frame}}





\begin{frame}

\begin{definition} \pause 
\begin{itemize}
\item $FP$ sei die Menge aller in Polynomzeit berechenbaren Wortfunktionen: \pause 
\[FP =  \bigcup_{p \textrm{Polynom}} FTIME(p)\]
\item  \pause  $P$ sei die Menge aller in Polynomzeit lösbaren Probleme: \pause 
\[P =   \bigcup_{p \textrm{Polynom}} TIME(p)\]

\end{itemize}

\end{definition} 

\only<article>{
 In Analogie kann man die Klasse der in exponentieller Zeit lösbaren Probleme definieren, 
 indem man als Zeitschranken Funktionen der Form $2^{c\cdot n}$ zulässt.
}
\only<presentation>{
 \pause  Analog: 

Klasse $EXP$ der in exponentieller Zeit lösbaren Probleme,  \pause \\
 mit Zeitschranken  $2^{c\cdot n}$
}
\end{frame}



\begin{frame}

\only<article>{
 Wir wollen den Zeitaufwand auch für nichtdeterministische Turingmaschinen definieren. 
}
\begin{definition}
Für eine nichtdeterministische Turingmaschine $M$  \pause sei 
    \GLA 
ntime_{M}(w) = \max\{&\textrm{ Schrittzahl irgendeiner Rechnung von }M
\\&\textrm{ bei Eingabe von }w\}
\GLE
\begin{itemize}
\item  \pause Sei $f:\nz\rightarrow\nz$ eine totale Zahlenfunktion.  \pause 

Die Klasse $NTIME(f)$ besteht  aus allen Sprachen $L$
über irgendeinem Alphabet  $E$ \pause 
 derart, dass es eine nichtdeterministische Mehrband-Turingmaschine $M$
 gibt mit $L(M) = L $ \pause 
und  $ntime_{M}(w)\leq f(|w|)$ für alle Eingaben $w$. \pause 
\item $NP  =  \bigcup_{p \textrm{Polynom}} NTIME(p)$
\end{itemize}
\end{definition}
\end{frame}


\only<article>{\begin{frame}

Für eine nichtdeterministische Turingmaschine $M$
gehören all diejenigen Wörter zu $L(M)$, 
für die es mindestens eine akzeptierende Berechnung der Maschine $M $
gibt. Wir verlangen bei der Definition der Zeitklasse $NTIME(f)$, 
dass die $M$ bei Eingabe eines Wortes $w $ der Länge $n $
also bei jeder möglichen Berechnung nach höchstens $f(n)$
Schritten aufhört zu rechnen, d.h. sie muss anhalten. 

Das kann entweder in einem Endzustand geschehen --- dann wird das Eingabewort akzeptiert. 

Oder sie hält in einem Nicht-Endzustand --- dann wird das Eingabewort nicht akzeptiert. 
\end{frame}}

\only<presentation>{\begin{frame}

$M$ nichtdeterministisch: \pause 
\begin{itemize}
\item
i.d.R. zu einer Eingabe $w$ viele mögliche Berechnungen,  \pause\\ oft unendlich lang \pause 
\item
$w\in L(M)\Longleftrightarrow$  \pause es gibt (mindestens) eine (endliche) akzeptierende Berechnung auf $w$
 \pause 
\item  $NTIME(f)$: \emph{jede} Berechnung hält nach maximal $f(|w|)$ Schritten \pause 

Keine unendlichen Berechnungen erlaubt, $M$ hält \emph{stets}! \pause 
\item Halt in Endzustand:  \pause Eingabewort $w$ akzeptiert.  \pause 
\item Halt (Steckenbleiben) in Nicht-Endzustand:   \pause $w$ nicht akzeptiert. 
\end{itemize}
\end{frame}}


\only<article>{\begin{frame}

Aus der Definition der Turingmaschinen ist sofort klar, dass $P$ in $NP$
enthalten ist. Ob jedoch $P = NP $ oder $P\neq NP $ ist, ist ein berühmtes offenes Problem, 
wohl das berühmteste Problem der theoretischen Informatik. 
Es wird als das  `$P$-$NP$-Problem' bezeichnet. 
Auf die Lösung dieses Problem ist seit dem Jahr 2000 ein Preis von 1 Million US Dollar ausgesetzt, siehe \url{http://www.claymath.org/millennium}.
 
Es gibt viele Probleme, die für die Praxis wichtig sind und in $NP$
liegen und von denen man gerne wüsste, ob sie auch in $P$ liegen. 
Wir werden in dem folgenden Kapitel sehen, dass es sogar viele Probleme gibt, nämlich die $NP$-vollständigen, die alle in $NP$ liegen und in dem folgenden Sinn typisch 
für das  $P$-$NP$-Problem sind: 

Könnte man schon für ein einziges von ihnen nachweisen, dass es auch in $P $ liegt oder dass es nicht in 
$P$ liegt, so hätte man damit schon das $P$-$NP$-Problem gelöst.
 
Da niemand trotz jahrzehntelanger Suche einen Polynomzeitalgorithmus für ein 
$NP$-vollständiges Problem gefunden hat, 
nehmen die meisten Wissenschaftler in der Komplexitätstheorie an, dass $P\neq NP $ ist. 

Wir werden uns in den folgenden Kapiteln auf das  $P$-$NP$-Problem konzentrieren. 
\end{frame}}



\only<presentation>{\begin{frame}
Nach Definition der Turingmaschinen sofort  \pause $P\subseteq NP$,  \pause offen jedoch: \pause 
\begin{block}{$P$-$NP$-Problem}
\[P\stackrel{?}{=}NP\]
\end{block}
\begin{itemize} \pause 
\item  berühmtestes Problem der theoretischen Informatik.  \pause 
\item Lösung wertvoll,  \pause Preisgeld 1 Million US-\$ \pause  \\ vgl. \url{http://www.claymath.org/millennium} \pause 
\item Grund: viele \emph{praktisch relevante Probleme} liegen in $NP$, \pause \\
für die keine brauchbaren Algorithmen bekannt sind \pause \\ 
(d.h. unbekannt ist, ob sie in $P$ liegen)  
\end{itemize}

\pause Spezielle große Problemklasse:  $NP$-vollständige Probleme \pause 
\begin{block}{}
Liegt auch nur ein $NP$-vollständiges Problem auch in $P$,  \pause so ist $P=NP$ \pause 

Liegt auch nur ein $NP$-vollständiges Problem \emph{nicht} in $P$,  \pause so ist $P\neq NP$ \pause 
\end{block}

Arbeitshypothese (z.B. für Kryptographie):  \pause Eher $P\neq NP$ als $P= NP$...
\end{frame}}




\begin{frame}

\only<article>{
 Vorher möchten wir aber noch zeigen, dass die Klasse $NP $
in einer deterministischen Zeitkomplexitätsklasse enthalten ist.
}

\begin{theorem} \pause 
Die Klasse $NP $ ist enthalten in   \pause   $\bigcup_{p \textrm{Polynom}}  TIME(2^{p(n)})$. \pause 
\end{theorem}
\only<article>{
Beweisskizze: Sei $L $ eine Sprache in $NP$. 
Dann gibt es ein Polynom $q $ und eine nichtdeterministische Turingmaschine $M$, 
die $L$ erkennt und in Zeit  $q(n)$ arbeitet. 
$M$ führt also bei jeder möglichen Rechnung zu einer Eingabe $w$
der Länge $n$ höchstens $q(n)$ Schritte durch. 
Alle möglichen Rechnungen, die $M$
bei einer festen Eingabe durchführen kann, kann man sich als Berechnungsbaum aufschreiben. 
Die Zahl der Verzweigungen an einem Knoten ist gerade die Zahl der verschiedenen Möglichkeiten, 
wie die Maschine von der Konfiguration aus weiterrechnen kann. 
Diese Zahl kann aber durch eine Konstante $c$, die nur von der \"Uberführungsfunktion von $M $
abhängt, nach oben beschränkt werden.  
Also hat der Berechnungsbaum höchstens $cq(n)$ Berechnungspfade. 
Eine geeignete deterministische Turingmaschine kann systematisch 
alle möglichen Rechnungen von $M$ mit Eingabe $w$ durchprobieren, 
also alle Pfade in diesem Berechnungsbaum daraufhin überprüfen, ob es einen akzeptierenden Pfad gibt. 
Das geht in Zeit, die nicht wesentlich grö"ser ist als $cq(n)$ , also für eine geeignetes Polynom $p$
 in Zeit $2^{p(n)}$. Also gibt es ein Polynom $p$, so dass $L$ in $TIME(2^{p(n)})$ enthalten ist. 
}
\only<presentation>{
Beweisskizze:  \pause Betrachte $L\in NP$  \pause 
\begin{itemize}
\item $M$ sei nichtdeterministische Turingmaschine mit $L(M)=L$ \pause 
\item $M$ arbeite auf Eingabe $w$ in Zeit  $\leq q(|w|)$ für Polynom $q$ \pause  
\item $c$ sei Maximalzahl möglicher Nachfolgekonfigurationen einer Konfiguration.  
\end{itemize}

\pause Betrachte Berechungsbaum $B_w$ aller Berechnungen von $M$ auf $w$  \pause 
\begin{itemize}
\item Knoten in $B_w$ sind markiert mit Konfigurationen von $M$ \pause 
\item Kante $(K,K')$ in $B_w$ entspricht Übergang $K\vdash K'$ bei $M$ \pause 
\item jeder Knoten  in $B_w$ hat Grad $\leq c$ \pause 
\item $B_w$ hat Tiefe $\leq q(|w|)$,  \pause also hat $B_w$ höchstens $c^{q(|w|)}$ Knoten
\end{itemize}
}
\end{frame}

\only<presentation>{\begin{frame}
Deterministischer Algorithmus für $L$: \pause 
\begin{itemize}
\item  Durchsuche $B_w$, ob akzeptierende Konfiguration enthalten \pause 
\item Wenn ja, akzeptiere $w$.  \pause 
\item Wenn nein, verwerfe $w$. 
\end{itemize}

\pause Da $\leq c^{q(|w|)}$ Knoten:  \pause Zeitaufwand $2^{p(|w|)}$ für Polynom $p$ \pause 

Damit $$L\in TIME(2^{p(n)})$$
\end{frame}}





\begin{frame}
\only<article>{
 Schlie"slich merken wir an, dass alle Sprachen in dieser Komplexitätsklasse und 
sogar in weit grö"seren Komplexitätsklassen nicht nur entscheidbar sind, 
sondern sogar LOOP-berechenbar. Dabei nennen wir eine Sprache $L $
LOOP-berechenbar, wenn die charakteristische Funktion der korrespondierenden 
Teilmenge $\nu^{-1}(L)$ der natürlichen Zahlen LOOP-berechenbar ist 
(hier ist $\nu$ die Bijektion zwischen natürlichen Zahlen und Wörtern aus \ref{Wort-Zahl}).
}
\only<presentation>{
Eine Sprache $L$ (aus Worten!) heißt LOOP-berechenbar,  \pause \\
wenn die charakteristische Funktion
der folgenden (Zahlen-!)Menge LOOP-berechenbar ist: \pause 
\[\nu^{-1}(L) \pause =\{n\in\nz\mid \nu(n)\in L\}\]
 \pause Damit:
}

\begin{theorem} \pause 
 Ist $f:\nz\rightarrow\nz$ eine LOOP-berechenbare Funktion, \pause \\
 so ist jede Sprache  $L$ aus $TIME(f)$ LOOP-berechenbar. 
\end{theorem}
\only<article>{
Beweisskizze: Sei $L$ aus $TIME(f)$ und $M$
eine Turingmaschine, die $L$ erkennt und in Zeit $f$ arbeitet. 
Da die Transformation zwischen einer Eingabe(-zahl) $n$ und  $\nu(n)$ nicht schwierig ist, 
kann man daraus eine Turingmaschine konstruieren, die die charakteristische Funktion der Menge 
$\nu^{-1}(L)$ in Zeit $g$ berechnet, wobei $g $
ebenfalls eine LOOP-berechenbare Funktion ist. 
}
\only<presentation>{
\pause Beweisskizze:  \pause Sei $L$ aus $TIME(f)$ \pause 
\begin{itemize}\item Betrachte Turingmaschine $M$ mit $L=L(M)$ \pause 
\item $M$ arbeite in Zeit $f(|w|)$ bei Eingaben $w$
\end{itemize}
\pause Konstruiere aus $M$ neue Turingmaschine $M'$ mit: \pause 
\begin{itemize}
\item $M'$ berechnet aus einer Eingabe $n\in\nz$ \pause 
(genauer: aus $u\in \{0,1\}^*$ mit $n=bin(u)$ ) \pause  zunächst
$w$ mit $w=\nu(n)  \pause =\nu(bin(u))$\pause
\item Danach wendet $M'$ die Maschine $M$ auf $w$ an. \pause 
\item Akzeptiert $M$, so gibt $M'$ eine $1$ aus,  \pause sonst eine $0$
\end{itemize}
}
\end{frame}

\only<presentation>{\begin{frame}
Also: \pause \begin{itemize}
\item
$M'$ berechnet die charakteristische Funktion von
$\nu^{-1}(L)$ \pause 
\item Achtung: Rechenzeit von $M'$ wird gemessen in $|u|$, d.h.  in $\log_2n$. 
\item \pause $M'$ arbeitet  in Zeit 
\[f'(|u|):=f(|w|) \pause +(\textrm{ Zeit zur Umwandlung }n\mapsto w)\]
\item  \pause Da $f$ LOOP-berechenbar ist, gibt es LOOP-berechenbares $g$ mit
$f'(|u|)\leq g(n)$
\end{itemize}

\end{frame}}



\only<article>{\begin{frame}
Wir hatten in Satz \ref{WHILE-Anzahl} gesehen, dass man eine Turingmaschine, die eine Zahlenfunktion berechnet, 
durch ein WHILE-Programm simulieren kann. 
Das WHILE-Programm konnte dabei so konstruiert werden, dass es nur eine einzige WHILE-Schleife enthielt. 
Au"serdem zeigt eine Analyse des Beweises, dass die Zahl der Durchläufe dieser 
WHILE-Schleife im Wesentlichen durch die Zahl der Rechenschritte der Turingmaschine beschränkt werden kann. 
Daher kann man in dem WHILE-Programm die WHILE-Schleife  

\texttt{~~~~~~~~~WHILE $x_z\neq 0$ DO}

 ersetzen durch 


\texttt{~~~~~~~~~$y:=g(n);$ LOOP $y$ DO}

Da die Funktion $g$ auch LOOP-berechenbar ist, 
kann man aus dem  WHILE-Programm daher ein äquivalentes LOOP-Programm erhalten. 

\end{frame}}






\only<presentation>{\begin{frame}
Aus Satz \ref{WHILE-Anzahl}:
\begin{itemize}
\item Zu $M'$ gibt es ein WHILE-Programm $WP$, das $M'$ simuliert \pause 
\item $WP$ hat dabei nur eine WHILE-Schleife  \pause \\
(mit Test auf den 'simulierten' Zustand $x_z$ von $M'$) \pause 
\item Ein Schleifendurchlauf bei $WP$ entspricht einem Schritt von $M'$ 
\end{itemize}

\pause Ersetze nun die WHILE-Schleife in $WP$  \pause 

\texttt{~~~~~~~~~WHILE $x_z\neq 0$ DO ...}

 \pause durch

\texttt{~~~~~~~~~$y:=g(n);$ LOOP $y$ DO IF $x_z\neq 0$ THEN ... END}

 \pause mit Resultat $WP'$ \pause 

$WP'$ berechnet ebenfalls $ch_{\nu^{-1}(L)}$ \pause 

$g$ ist LOOP-berechenbar,  \pause also ist auch $WP'$ LOOP-berechenbar!

\end{frame}}


\begin{frame}
\only<article>{Zum Beispiel sind alle Polynome $p$ und auch alle Funktionen der Form $2^{p(n)}$  ($p$
Polynom) LOOP-berechenbar. 
 
Das folgende Diagramm gibt die Situation nach dem heutigen Stand der Kenntnisse und Vermutungen wieder.
}
\only<presentation>{Beispiele:  \pause \begin{itemize}
\item alle Polynome $p$ sind LOOP-berechenbar \pause 
\item alle Funktionen der Form $2^{p(n)}$  (mit 
Polynom $p$) sind LOOP-berechenbar. 
\end{itemize}
 \pause Damit sind alle Mengen in $P$ oder $NP$ auch LOOP-berechenbar! \pause 

Aktueller Stand der Kenntnisse und Vermutungen: \pause 
}

\[\multiinclude[graphics={width=21em}]{grafik/NP1}\]
\end{frame}
