\section{Komplexitätsklassen und das $P$-$NP$-Problem} \inhalta{9-15} \only
{\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{\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
{\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
{(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{ (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
{ (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{ (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
{\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
{ 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{ \pause Analog: Klasse $EXP$ der in exponentieller Zeit lösbaren Probleme, \pause \\ mit Zeitschranken $2^{c\cdot n}$ } \end{frame} \begin{frame} \only
{ 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
{\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{\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
{\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{\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
{ 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
{ 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{ 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{\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
{ 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{ 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
{ 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{ \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{\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
{\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{\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
{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{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}