{"id":1390,"date":"2013-05-01T19:54:45","date_gmt":"2013-05-01T17:54:45","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1390"},"modified":"2025-11-25T23:16:58","modified_gmt":"2025-11-25T22:16:58","slug":"tib-separations-und-hierarchiesatze-lernziele-ke2","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1390","title":{"rendered":"TIB: Separations- und Hierarchies\u00e4tze (Lernziele KE2, Update 2)"},"content":{"rendered":"

Update 4<\/strong>: MathJax wollte nicht so, wie ich oder einige Leser des Blogs. Nun sollten alle Symbole wieder angezeigt werden.<\/p>\n

Update 3<\/strong>: Ein kleiner Exkurs zum Thema \\(P-NP\\) wurde hinzugef\u00fcgt<\/a>.<\/p>\n

Update 2<\/strong>: Zwei Fehler in der Berechnung im Lernziel 3 sind nun gefixt.<\/p>\n

Update<\/strong>: Antworten zu Lernzielen hinzugef\u00fcgt. Soweit m\u00f6glich.<\/p>\n

Lernziel 1<\/h2>\n

Verstehen des Verfahrens von Separations- und Hierarchies\u00e4tzen<\/em><\/p>\n

(Gro\u00dfer Dank an Barbara, Oliver, Bj\u00f6rn und Lothar aus der NG f\u00fcr die Tipps zu diesem Thema).<\/p>\n

Zun\u00e4chst: was sind Hierarchies\u00e4tze und wof\u00fcr werden sie gebraucht? Der Satz aus der Wikipedia<\/a> ist hier durchaus hilfreich:<\/p>\n

F\u00fcr die gebildeten Klassen m\u00f6chte man m\u00f6glichst beweisen, dass durch zus\u00e4tzlich bereitgestellte Ressourcen tats\u00e4chlich mehr<\/i> Probleme gel\u00f6st werden k\u00f6nnen. Diese Beweise bezeichnet man als Hierarchies\u00e4tze<\/i> (auch Separationss\u00e4tze<\/i> genannt), da sie auf den Klassen der jeweiligen Ressource eine Hierarchie induzieren. Es gibt also Klassen, die in eine echte Teilmengenbeziehung gesetzt werden k\u00f6nnen. Wenn man solche echten Teilmengenbeziehungen ermittelt hat, lassen sich auch Aussagen dar\u00fcber treffen, wie gro\u00df die Erh\u00f6hung einer Ressource sein muss, um damit eine gr\u00f6\u00dfere Zahl von Problemen berechnen zu k\u00f6nnen.<\/p>\n

…<\/p>\n

Die Hierarchies\u00e4tze bilden letztlich das Fundament f\u00fcr die Separierung<\/i> von Komplexit\u00e4tsklassen. Sie bilden einige der fr\u00fchesten Ergebnisse der Komplexit\u00e4tstheorie.<\/p>\n

…<\/p><\/blockquote>\n

D.h. wir haben hier die M\u00f6glichkeit Komplixit\u00e4tsklassen von einander trennen zu k\u00f6nnen (wenn bestimmte Vorbedingungen erf\u00fcllt sind), so dass eine echte Inklusion erf\u00fcllt ist.<\/p>\n

Bevor wir hier weitermachen, wiederholen wir noch einmal ein paar Kleinigkeiten aus den vorhergehenden Beitr\u00e4gen zum Thema Sprache:<\/p>\n

Eine Sprache \\(L(M)\\) ist entscheidbar<\/strong> wenn die charakteristische Funktion<\/p>\n

\\(\\chi_L(\\omega)=\\begin{cases}1&\\text{ falls }\\omega\\in{L}\\\\0&\\text{ falls }\\omega\\notin{L}\\end{cases}\\)<\/p>\n

berechenbar ist. Es gibt noch die Definition mit „…h\u00e4lt f\u00fcr jede Eingabe.<\/em>„, was nat\u00fcrlich auch korrekt ist.<\/p>\n

Wir k\u00f6nnen diese Maschine so modifizieren, dass sie eine \\(1\\)$ ausgibt bevor sie im akzeptierenden Zustand h\u00e4lt oder in einem nicht-akzeptierenden Zustand h\u00e4lt und eine \\(0\\) vorher ausgibt. Wie wir bald erfahren werden, ist das Wortproblem f\u00fcr \\(Typ-1\\)-Sprachen entscheidbar.<\/p>\n

Beispiel<\/strong>: \\(L=\\{a^n\\mid n>10\\}\\). Wir k\u00f6nnen f\u00fcr jede Eingabe \\(x\\) entscheiden ob \\(x\\) den Einschr\u00e4nkungen gen\u00fcgt oder nicht.<\/p>\n

Eine Sprache \\(L(M)\\) ist aufz\u00e4hlbar <\/b>wenn die charakteristische Funktion<\/p>\n

\\({\\chi_L}^{‚}(\\omega)=\\begin{cases}1&\\text{ falls }\\omega\\in{L}\\\\\\perp&\\text{ falls }\\omega\\notin{L}\\end{cases}\\)<\/p>\n

berechenbar ist. Auch hier greife ich etwas vor: das Wortproblem f\u00fcr \\(Typ-0\\)-Sprachen ist nur semi-entscheidbar.<\/p>\n

Beispiel<\/strong>: Halteproblem\\(L=\\{i\\#x\\mid M_i\\text{ haelt auf }x\\}\\) ist rekursiv aufz\u00e4hlbar. Hier besteht das Wort unserer Sprache aus \\(i\\#x\\), wobei \\(i\\) die Codierung einer \\(TM\\) ist und \\(x\\) die Eingabe dazu. Da wir nicht entscheiden k\u00f6nnen, ob die Maschine \\(M_i\\) bei der Eingabe von \\(x\\) nicht h\u00e4lt, ist auch unsere daraus erstellte Sprache nur rekursiv aufz\u00e4hlbar.<\/p>\n

Nun haben wir uns noch einmal klar gemacht, was eine Sprache ist und wann man sie als entscheidbar\/rekursiv aufz\u00e4hlbar klassifizieren kann. Jetzt k\u00f6nnen wir \u00fcber Komplexit\u00e4tsklassen reden.<\/p>\n

Beweis: Unterschiedlichkeit der Komplexit\u00e4tsklassen<\/strong><\/p>\n

(Danke an Lothar f\u00fcr die geduldige Erkl\u00e4rung der Vorbedingungen)<\/p>\n

Wie beweisen wir die Unterschiedlichkeit von Komplexit\u00e4tsklassen? Dass z.B. \\(ZEIT(n)\\subsetneqq ZEIT(n^2)\\) ist? Mittels Diagonalisierung und universellen Maschinen. Bei dem Diagonalisierungsbeweis wird ein \u00e4hnliches Verfahren verwendet wie beim Selbstanwendbarkeitsproblem (spezielles Halteproblem, wir erinnern<\/a> uns?): die Diagonalisierung erfolgt nicht \u00fcber alle rekursiven Mengen, sondern \u00fcber die Mengen in \\(ZEIT(f)\\). Ben\u00f6tigt wird hierzu:<\/p>\n

1. eine universelle, \\(f\\)-zeitbeschr\u00e4nkte Maschine (diese wird verwendet um zu pr\u00fcfen, ob sich eine Menge in einer bestimmten Zeitschranke befindet)<\/p>\n

2. ein Komplexit\u00e4tsklasse mit Zeitschranke \\(g\\)<\/p>\n

Der Beweis beim Zeitseparationssatz<\/strong> (\\(ZEIT(g)\\nsubseteqq ZEIT(f)\\)) besteht im Grunde darin eine Menge \\(D\\) zu konstruieren, die zwar in \\(ZEIT(g)\\) liegt, aber nicht in \\(ZEIT(f)\\). Das erfolgt als Diagonalbeweis indem man durch einen Widerspruch zun\u00e4chst zeigt, dass die Menge \\(D\\notin{ZEIT(f)}\\) ist, was durch unsere universelle Maschine mit Laufzeit \\(f(n)\\cdot log\\text{ }f(n)\\) entschieden wird.<\/p>\n

Fazit: wir simulieren also eine Maschine, die die Sprache aus der Menge \\(ZEIT(g)\\) (also eine Sprache, die in Laufzeit \\(O(g)\\) entschieden wird) auf einer universellen Maschine entscheidet, die durch \\(f\\) beschr\u00e4nkt ist. Wenn wir \u00fcber die Beschr\u00e4nkung, die uns \\(f\\) auferlegt laufen, so ist die Sprache nicht in \\(ZEIT(f)\\).<\/p>\n

Die schnellste Simulation einer \\(k\\)-Band Maschine durch eine universelle \\(2\\)-Band Maschine hat die Laufzeit \\(O(f(n)\\cdot log\\text{ }f(n))\\), was klar ist: wir m\u00fcssen zun\u00e4chst die Maschine selbst simulieren (Faktor \\(f(n)\\)) und dann die \\(k\\) B\u00e4nder auf 2 B\u00e4nder verkleinern (Faktor \\(log f(n)\\)). W\u00fcrden wir nur ein Arbeitsband verwenden, so w\u00e4re der Aufwand nicht mehr \\(log\\text{ }f(n)\\), sondern \\(f(n)^2\\) (siehe KE1).<\/p>\n

Aus diesem Grund fordern wir auch, dass \\(g\\notin O(f(n)\\cdot log\\text{ }f(n))\\) ist damit wir die Sprache mit der Schranke \\(g\\) auf unserer Maschine entscheiden k\u00f6nnen. W\u00e4re \\(g\\in O(f(n)\\cdot log\\text{ }f(n))\\), so k\u00f6nnten wir nicht pr\u00fcfen ob die Sprache akzeptiert wird, da unsere universelle Maschine f\u00fcr die Pr\u00fcfung zu langsam ist, denn die hat genau die Laufzeit, wo auch \\(g\\) drin w\u00e4re. Die universelle Maschine h\u00e4tte also nicht genug Zeit die zu simulierende Maschine zu simulieren um die Akzeptanz der Sprache zu pr\u00fcfen. Uah, was f\u00fcr ein Satz!<\/p>\n

Anschlie\u00dfend erfolgt der Nachweis, dass \\(D\\in{ZEIT(f)}\\) indem wir eine Maschine angeben, die durch \\(f\\) beschr\u00e4nkt ist und dennoch \\(D\\) entscheiden kann und die Unterschiedlichkeit der zwei Komplexit\u00e4tsklassen ist bewiesen.<\/p>\n

Der Beweis f\u00fcr den Zerhierarchiesatz<\/strong> (\\(ZEIT(f)\\subsetneq ZEIT(g)\\)) erfolgt genauso, nur wird vorausgesetzt, dass \\(f\\) mindestens das gleiche Wachstum, wie \\(g\\) hat: \\(f\\in{O(g)}\\).<\/p>\n

Antwort zum Lernziel<\/strong>: Zeithierarchie- und separationss\u00e4tze dienen dazu Komplexit\u00e4tsklassen von einander zu trennen. Im Endeffekt geht es um Separierung und der Bildung von Hierarchien bei den Ressourcen Band und Zeit.<\/p>\n

Was ist also unser Zeithierarchie- oder separationssatz? Schreiben wir sie uns zun\u00e4chst einmal auf (ich empfehle euch, dass Ihr das auf dem Papier auch macht):<\/p>\n

Lernziel 2<\/h2>\n

Voraussetzung f\u00fcr Separations- und Hierarchies\u00e4tze benennen und begr\u00fcnden<\/em><\/p>\n

Zeitseparationssatz<\/strong>:<\/p>\n

Sei \\(f, g: \\mathbb{N}\\rightarrow\\mathbb{N}\\), \\(g\\) zeitkonstruierbar, \\(n\\in O(g)\\), \\(g\\notin O(f(n)\\cdot\\text{ }log f(n))\\).<\/p>\n

Dann ist \\(ZEIT(g)\\nsubseteqq ZEIT(f)\\)<\/p><\/blockquote>\n

Damit \\(ZEIT(g)\\) keine<\/strong> Teilmenge<\/strong> von  \\(ZEIT(f)\\) ist, m\u00fcssen einige Voraussetzungen erf\u00fcllt sein. Diese sind:<\/p>\n

1. Wir haben ein \\(g\\), dass zeitkonstruierbar ist (die maximale Schrittzahlfunktion der \\(TM\\) von \\(g\\) hat als obere Schranke das Wachstum von \\(g\\) f\u00fcr alle Eingaben, siehe unten),<\/p>\n

2. ein \\(n\\in O(g)\\), \\(n\\) bedeutet hier, dass \\(g\\) mindestens linear w\u00e4chst (k\u00f6nnten wir weglassen, da es bereits beim Lesen der Eingabe auf der universellen Maschine erreicht wird)<\/p>\n

3. ein \\(g\\), dass sich nicht in \\(O(f(n)\\cdot log\\text{ }f(n))\\) befindet. D.h. \\(g\\) hat als obere Schranke nicht <\/strong>\\(O(f(n)\\cdot log\\text{ }f(n))\\) (der Grund ist, dass sich die durch \\(f\\) beschr\u00e4nkte, zu simulierende Maschine mindestens in \\(O(f(n)\\cdot\\text{ }log f(n))\\) simulieren l\u00e4sst. W\u00e4re \\(g\\) noch in der oben angegebenen Schranke, k\u00f6nnten wir nicht entscheiden ob die Sprache aus \\(ZEIT(g)\\) sich in \\(ZEIT(f)\\) befindet).<\/p>\n

Wir separieren also die Komplexit\u00e4tsklassen der beiden Funktionen von einander wenn die oben genannten Voraussetzungen erf\u00fcllt sind.<\/p>\n

Zeithierarchiesatz:<\/strong><\/p>\n

Sei \\(g: \\mathbb{N}\\rightarrow\\mathbb{N}\\) zeitkonstruierbar, \\(n\\in O(g)\\), \\(f: \\mathbb{N}\\rightarrow\\mathbb{N}, f\\in O(g), g\\notin O(f(n)\\cdot{log\\text{ }f(n)})\\).<\/p>\n

Dann ist \\(ZEIT(f)\\subsetneqq ZEIT(g)\\)<\/p><\/blockquote>\n

Damit \\(ZEIT(f)\\) eine echte<\/strong> Teilmenge<\/a><\/strong> von  \\(ZEIT(g)\\) ist, m\u00fcssen auch hier einige Voraussetzungen gelten. Nehmen wir sie auch hier auseinander:<\/p>\n

1. Wir haben auch hier ein \\(g\\), dass zeitkonstruierbar ist,<\/p>\n

2. ein \\(n\\in O(g)\\), \\(n\\) bedeutet hier, dass \\(g\\) mindestens linear w\u00e4chst<\/p>\n

3. ein \\(f\\), dass \\({}\\in O(g)\\) ist (\\(g\\) w\u00e4chst damit mindestens so schnell wie \\(f\\)), w\u00e4hrend sich das<\/p>\n

4. \\(g\\) nicht in \\(O(f(n)\\cdot log\\text{ }f(n))\\) befindet (\\(g\\) w\u00e4chst schneller als \\(O(f(n)\\cdot log\\text{ }f(n))\\)).<\/p>\n

Wir wir sehen k\u00f6nnen, sind das fast die selben Vorbedingungen wie f\u00fcr den Separationssatz. Damit \\(ZEIT(f)\\) jedoch eine Teilmenge sein kann, muss sich \\(f\\) zus\u00e4tzlich in \\(O(g)\\) befinden. Erst dann gilt: \\(ZEIT(f)\\subsetneqq ZEIT(g)\\). Was haben wir hier am Ende getan? Wir haben eine Hierarchie zwischen den beiden Komplexit\u00e4tsklassen geschaffen, so dass \\(ZEIT(f)\\) eine echte Teilmenge von \\(ZEIT(g)\\) darstellt.<\/p>\n

Weil es wo sch\u00f6n war: noch einmal den ganzen Spa\u00df mit dem Bandhierarchie- und dem Bandseparationssatz:<\/p>\n

Bandseparationssatz<\/strong>:<\/p>\n

Sei \\(g: \\mathbb{N}\\rightarrow\\mathbb{N}\\), \\(g\\) bandkonstruierbar, \\(log\\in O(g)\\), \\(f:\\mathbb{N}\\rightarrow\\mathbb{N}\\).<\/p>\n

Dann gilt \\(BAND(g)\\subseteq BAND(f)\\Leftrightarrow g\\in O(f)\\)<\/p><\/blockquote>\n

Damit \\(BAND(g)\\) eine<\/strong> Teilmenge<\/strong> (im Gegensatz zu „keine Teilmenge“ beim Zeitseparationssatz) von  \\(BAND(f)\\) ist und \\(f\\) als obere Schranke f\u00fcr das bandbedarfswachstum \\(g\\) gilt, m\u00fcssen folgende Voraussetzungen erf\u00fcllt sein:<\/p>\n

1. ein bandkonstruierbares \\(g\\) (\\(\\tilde{s}_M\\), d.h. der maximale Speicher- bzw. Bandbedarf der Maschine muss in der Komplexit\u00e4tsklasse von \\(O(g)\\) liegen),<\/p>\n

2. \\(log\\in O(g)\\), \\(g\\) w\u00e4chst also mindestens logarithmisch und wir haben ein<\/p>\n

3. ein \\(f\\) mit Definitions- und Bildmenge aus \\(\\mathbb{N}\\).<\/p>\n

4. Dazu ist \\(f\\) eine obere Schranke f\u00fcr \\(g\\)<\/p>\n

Auch hier haben wir eine Separation des Bandbedarfs, genauer der Komplexit\u00e4tsklassen des Bandbedarfs von Funktionen \\(f\\) und \\(g\\) und k\u00f6nnen zudem auch sagen, dass die obere Schranke f\u00fcr das Bandbedarfswachstum von \\(g\\) eben \\(O(f)\\) ist. Ist ja auch klar, denn es gilt (wenn die Voraussetzungen erf\u00fcllt sind) \\(BAND(g)\\subseteq BAND(g)\\).<\/p>\n

Kommen wir nun zum Bandhierarchiesatz:<\/p>\n

Bandhierarchiesatz<\/strong>:<\/p>\n

Sei \\(log\\in O(g)\\), \\(g\\) bandkonstruierbar, \\(f\\in O(g)\\), \\(g\\notin O(f)\\).<\/p>\n

Dann gilt \\(BAND(f)\\subsetneqq{BAND(g)}\\)<\/p><\/blockquote>\n

Damit \\(BAND(f)\\) also eine<\/strong> echte Teilmenge<\/strong> von  \\(BAND(g)\\) darstellt, k\u00e4mpfen wir mit den folgenden Voraussetzungen: notwendig sind<\/p>\n

1. ein bandkonstruierbares \\(g\\) (siehe oben),<\/p>\n

2. \\(log\\in O(g)\\), \\(g\\) w\u00e4chst also mindestens logarithmisch, wir haben ein<\/p>\n

3. ein \\(f\\in O(g)\\), d.h. \\(f\\) hast \\(g\\) als obere Schranke und<\/p>\n

4. ein \\(g\\notin O(f)\\), also ist \\(f\\) keine<\/strong> obere Schranke f\u00fcr \\(g\\)<\/p>\n

Mit dem Hierarchiesatz haben wir es auch hier geschafft eine Hierarchie auf den Komplexit\u00e4tsklassen des Bandbedarfs herzustellen. W\u00e4hrend wir beim Separationssatz durchaus gleiche Mengen haben k\u00f6nnten (z.B. ist \\(\\{1,2,3\\}\\) eine Teilmenge<\/strong> von \\(\\{1,2,3\\}\\)) , haben wir das beim Hierarchiesatz nicht (\\(\\{1,2\\}\\) eine echte Teilmenge<\/strong> von \\(\\{1,2,3\\}\\)). Bitte macht euch nochmal den Unterschied klar.<\/p>\n

Antwort zum Lernziel<\/strong>: Die Voraussetzungen f\u00fcr Separation und Hierarchie begr\u00fcnden sich in der \\(TM\\), auf denen die Funktion simuliert wird.<\/p>\n

F\u00fcr die Separation<\/strong> von \\(g\\) und \\(f\\) muss \\(g\\) zeitkonstruierbar sein (Schrittzahlfunktion der \\(TM\\) muss noch innerhalb der Schranke der Funktion liegen), min. lineares Wachstum haben (da die Eingabe von der \\(TM\\) gelesen werden muss und wir z.B. beim Lesen von \\(n\\) durch die Un\u00e4rnotation schon \\(n\\) Schritte verbrauchen) und sich nicht in \\(O(f(n)\\cdot log f(n))\\) (da wir die \\(f\\)-beschr\u00e4nkte Maschine simulieren m\u00fcssen und die Simulation bereits in \\(O(f(n)\\cdot log\\text{ }f(n))\\) erfolgt) befinden.<\/p>\n

Bei der Hierarchie<\/strong> haben wir \u00e4hnliche Vorbedingungen, m\u00fcssen aber zus\u00e4tzlich sicherstellen, dass die zu untersuchende Funktion \\(f\\) innerhalb der Schranke f\u00fcr \\(g\\) liegt.<\/p>\n

Die Selbsttestaufgabe aus dem Skript ist hier anschaulich, ich m\u00f6chte mich daher auch in dem Beitrag daran halten.<\/p>\n

Lernziel 3<\/h2>\n

Anwendung der S\u00e4tze zum Beweis von Separationen und echten Inklusionen<\/em><\/p>\n

Beispiel<\/strong><\/p>\n

\\(f(n)=\\begin{cases}n, &\\mbox{falls }n\\mbox{ gerade}\\\\n^3, &\\mbox{sonst}\\end{cases}\\)<\/p>\n

\\(g(n) = n^2\\)<\/p>\n

Beide Funktionen sind zeitkonstruierbar. Behauptung:<\/p>\n

(1) \\(ZEIT(f)\\subseteq ZEIT(g)\\)<\/p>\n

Wir ben\u00f6tigen hier also unseren Zeitseparationssatz<\/strong>:<\/p>\n

Sei \\(f, g: \\mathbb{N}\\rightarrow\\mathbb{N}\\), \\(g\\) zeitkonstruierbar, \\(n\\in O(g)\\), \\(g\\notin O(f(n)\\cdot\\text{ }log f(n))\\). Dann ist \\(ZEIT(g)\\nsubseteqq ZEIT(f)\\)<\/p><\/blockquote>\n

Fangen wir mit Behauptung (1)<\/strong> an: \\(ZEIT(f)\\subseteq ZEIT(g)\\)<\/p>\n

Wir setzen \\(g=n\\) oder \\(g=n^3\\) je nach Fall. Und \\(f=n^2\\)<\/p>\n

(im Satz wird ja nicht \\(ZEIT(f)\\nsubseteqq ZEIT(g)\\), sondern \\(ZEIT(g)\\nsubseteqq ZEIT(f)\\) gepr\u00fcft).<\/p>\n

Vorbedingungen, die wir erf\u00fcllen m\u00fcssen f\u00fcr den Zeitseparationssatz sind also:<\/p>\n

1. \\(g\\) muss zeitkonstruierbar sein: check!<\/p>\n

2. \\(g\\) muss mindestens lineares Wachstum haben: check!<\/p>\n

3. die obere Schranke f\u00fcr \\(g\\) ist nicht \\(O(f(n)\\cdot log\\text{ }f(n))\\): auch wenn man das sieht, pr\u00fcfen wir das doch mal:<\/p>\n

Fall 1<\/span><\/p>\n

Wenn \\(n\\) gerade, muss gelten: \\(n\\notin O(n^2\\cdot log(n^2))\\). Gilt es? Nein!<\/p>\n

Fall 2<\/span><\/p>\n

Ist \\(n\\) ungerade, muss gelten: \\(n^3\\notin O(n^2\\cdot log(n^2))\\). Gilt dies? Ja! Die Voraussetzung ist hier also erf\u00fcllt.<\/p>\n

Da bei einem ungeraden \\(n\\) die Voraussetzungen f\u00fcr die Separation gegeben sind, ist \\(ZEIT(f)\\nsubseteqq ZEIT(g)\\). H\u00e4tten wir nur ein \\(n\\) statt \\(n^3\\), so w\u00e4re die Voraussetzung nicht gegeben. Aber so gilt der Separationssatz f\u00fcr ungerade \\(n\\) und damit ist Behauptung (1) falsch.<\/p>\n

Antwort zum Lernziel<\/strong>: Siehe oben. Auf zwei gegebene Funktionen \\(f\\) und \\(g\\) kann man die Zeit- und Bandhierarchies\u00e4tze anwenden (wenn die Voraussetzungen zutreffen) und so eine Hierarchie oder eine Separierung der Komplexit\u00e4tsklassen vornehmen.<\/p>\n

Lernziel 4<\/h2>\n

Definition von band- und zeitkonstruierbaren Funktionen<\/em><\/p>\n

Was ist eine band- bzw. zeitkonstruierbare Funktion? Das Wachstum so einer Funktion entspricht dem Bandbedarf, bzw. der Schrittzahlfunktion eine real existierenden Turingmaschine. Was man sich merken sollte ist, dass zwar alle zeitkonstruierbaren Funktionen bandkonstruierbar sind. Andersherum geht es aber nicht. Das folgt aufgrund des Zusammenhangs zwischen Band und Zeit<\/a>. Hangeln wir uns an der Definition entlang:<\/p>\n

\\(f: \\mathbb{N} \\rightarrow\\mathbb{N}\\) hei\u00dft bandkonstruierbar<\/strong>, falls es eine TM \\(M\\) gibt, so dass \\(\\forall n. f_M(0^n) = 0^{f(n)}, \\tilde{s}_M\\in O(f)\\)<\/p><\/blockquote>\n

Was muss vorliegen damit die Funktion bandkonstruierbar<\/strong> ist? \\(\\tilde{s}_M\\), d.h. der maximale Speicher- bzw. Bandbedarf der Maschine muss in der Komplexit\u00e4tsklasse von \\(O(f)\\) liegen.<\/p>\n

\\(f: \\mathbb{N} \\rightarrow\\mathbb{N}\\) hei\u00dft zeitkonstruierbar<\/strong>, falls es eine TM \\(M\\) gibt, so dass \\(\\forall n. f_M(0^n) = 0^{f(n)}, \\tilde{t}_M\\in O(f)\\)<\/p><\/blockquote>\n

Hier ist es \u00e4hnlich. Nochmal zur Erinnerung: \\(\\tilde{t}_M\\) ist die maximale<\/strong> Anzahl der Schritte, die die TM \\(M\\) ben\u00f6tigt um bei der Eingabe eines Wertes die Endkonfiguration zu erreichen und \\(0^n\\) ist die Un\u00e4rnotation von \\(n\\) (z.B. \\(5 = 00000\\)).<\/p>\n

Nicht vergessen: \\(t_M \\neq \\tilde{t}_M\\). Ersteres bezeichnet n\u00e4mlich nur die Anzahl der Schritte bis zur Endkonfiguration bei einer bestimmten Angabe, letzteres die maximale Anzahl der Schritte bei allen Eingaben (\\(\\tilde{t}_M := max\\{t_M(x)|x\\in \\Sigma^n\\}\\)).<\/p>\n

Was m\u00fcssen wir also tun um zu zeigen, dass eine Funktion \\(f\\) zeitkonstruierbar ist? Die Aufgabe im Skript zeigt es relativ anschaulich, dem will ich mich also auch nicht verschlie\u00dfen.<\/p>\n

Beispiel<\/strong>: zeigen, dass \\(f(n) = \\lfloor n \\cdot \\sqrt{n} \\rfloor\\) zeitkonstruierbar ist.<\/span><\/p>\n

Wir schauen in die Definition und merken, dass wir eine TM angeben m\u00fcssen, deren Schrittzahlfunktion f\u00fcr alle Eingaben von \\(n\\) innerhalb der Schranke \\(O(\\lfloor n \\cdot \\sqrt{n} \\rfloor)\\) liegt. In dem Beispiel wird auch mit Dualzahlen gerechnet anstatt mit der un\u00e4ren Notation von \\(n\\). Also nicht davon abschrecken lassen, d.h. \\(d(n)\\) ist die Dualnotation von \\(n\\) (z.B. \\(d(5) = 101\\)). Lange Rede, kurzer Sinn: es m\u00fcssen also folgende Voraussetzungen f\u00fcr die Zeitkonstruierbarkeit erf\u00fcllt sein:<\/p>\n

1. \\(f_M(0^n) = 0^{f(n)}\\), z.B. \\(f_M(0^5) = 0^{11}\\) (die TM berechnet also die Funktion und gibt sie in un\u00e4rer Notation aus) und<\/p>\n

2. \\(\\tilde{t}_M\\in O(f)\\), die Schrittzahlfunktion der TM liegt innerhalb der Schranke \\(O(f)\\), d.h. \\(O(\\lfloor n \\cdot \\sqrt{n} \\rfloor)\\)<\/p>\n

Nochmal zum selber nachrechnen: \\(f(\\lfloor n \\cdot \\sqrt{n} \\rfloor)\\) mit \\(n = 5 = 0^5 \\rightarrow f(5) = 11\\), \\(f(0^5) = 0^{11}\\). Die Schritte, die zu der korrekten Berechnung im Skript gemacht werden sind:<\/p>\n

1. Berechnung von \\(a = d(n)\\)<\/p>\n

2. Berechnung von \\(b= a*a*a\\)<\/p>\n

3. Berechnung von \\(c=d(\\lfloor\\sqrt{d^ {-1}(b)}\\rfloor)\\)<\/p>\n

4. Ausgabe von \\(0^{d^{-1}(c)}\\)<\/p>\n

Probieren wir das mal am Beispiel \\(n = 5\\)<\/p>\n

1. \\( a = d(5) = 101\\)<\/p>\n

2. \\(b = 101 * 101 * 101 = 1111101\\)<\/p>\n

3. \\( c =d(\\lfloor\\sqrt{d^ {-1}(1111101)}\\rfloor) = 1011\\)<\/p>\n

4. Ausgabe von \\(0^{d^{-1}(1011)} = 0^{11} = 00000000000\\)<\/p>\n

Sieht also gut aus. Damit haben wir eine funktionierende TM f\u00fcr die Funktion und m\u00fcssen nur noch schauen ob die Schritte bis zur Endkonfiguration, d.h. bis zu unseren Ausgabe auch in der Schranke \\(O(f)\\), d.h. \\(O(\\lfloor n \\cdot \\sqrt{n} \\rfloor)\\) liegen:<\/p>\n

1. hier brauchen wir \\(O(n)\\) Schritte<\/p>\n

2. f\u00fcr die Multiplikation reicht die Schulmethode, welche uns zu \\(O((log n)^2)\\) bringt.<\/p>\n

3. mit der Intervallschachtelung kommen wir hier mit \\(O((log n)^3)\\) Schritten aus.<\/p>\n

4. f\u00fcr den letzten Schritt, die un\u00e4re Ausgabe werden mehr Schritte ben\u00f6tigt als bei den drei Schritten davor: \\(O(\\lfloor n \\cdot \\sqrt{n} \\rfloor)\\).<\/p>\n

Damit dominiert dieser Schritt die Rechenzeit und wir haben gezeigt, dass \\(O(f(n)) = O(\\lfloor n \\cdot \\sqrt{n} \\rfloor)\\) und damit zeitkonstruierbar ist.<\/p>\n

Wenn wir das Beispiel nachvollziehen konnten, so ist auch klar geworden, dass z.B. die Funktionen \\(log n\\) und \\(\\lfloor\\sqrt{n}\\rfloor\\) nicht zeitkonstruierbar sind, denn sie ben\u00f6tigen mehr Schritte zur Berechnung als \\(log n\\) und \\(\\lfloor\\sqrt{n}\\rfloor\\) und passen daher nicht in die oberen Schranken, die wir f\u00fcr die Zeitkonstruierbarkeit ben\u00f6tigen.<\/p>\n

Antwort zum Lernziel<\/strong>: F\u00fcr eine Zeit- und Bandkonstruktion bei einer Funktion \\(f\\) m\u00fcssen wir zeigen, dass die maximale Schrittzahlfunktion \\(\\tilde{t}_M\\) und der maximale Speicherplatzbedarf \\(\\tilde{s}_M\\) innerhalb der Schranke \\(O(f)\\) liegt. Ist uns das gelungen ist die Funktion \\(f\\) zeit- bzw. bandkonstruierbar.<\/p>\n

Lernziel 5<\/h2>\n

Beschreibung des Beweises von \\(ZEIT(n)\\subsetneqq{ZEIT(n\\cdot log\\text{ }n)}\\)<\/em><\/p>\n

Antwort zum Lernziel<\/strong>: Hier muss ich erstmal passen. Wer eine sch\u00f6ne Beschreibung der Beweisidee hat, bitte melden.<\/p>\n

Lernziel 6<\/h2>\n

Beweis der Beziehungen zwischen den Klassen P, LOGSPACE, PSPACE<\/em><\/p>\n

Um die Beziehungen zwischen P, LOGSPACE und PSPACE zu verstehen, m\u00fcssen wir zun\u00e4chst einmal wissen, was P, LOGSPACE und PSPACE ist. Fangen wir mit der Klasse P an:<\/p>\n

\\(P:=\\bigcup_{k\\in\\mathbb{N}} ZEIT(n^k)\\)<\/p>\n

Was das? Die Klasse \\(P\\) ist die unendliche Vereinigung der Zeitkomplexit\u00e4tsklassen \\(ZEIT(f)\\). In der Literatur wird sie auch Polynomialzeit<\/a> genannt. Es bezeichnet die Klasse der effizient l\u00f6sbaren Probleme. \\(P\\) ist eine Teilmenge von \\(NP\\), d.h. \\(P\\subseteq NP\\) (hier kommt auch das ber\u00fchmte P-NP-Problem<\/a> her), aber dazu sp\u00e4ter mehr. Dann haben wir noch:<\/p>\n

\\(PSPACE:=\\bigcup_{k\\in\\mathbb{N}} BAND(n^k)\\)<\/blockquote>\n

Und das ist eine unendliche Vereinigung der Bandkomplexit\u00e4tsklassen \\(BAND(f)\\). Letztendlich haben wir auch noch:<\/p>\n

\\(LOGSPACE:=\\bigcup_{k\\in\\mathbb{N}} BAND(log)\\)<\/blockquote>\n

\\(LOGSPACE\\) gilt als die kleinste Bandkomplexit\u00e4tsklasse.<\/p>\n

Die Beziehung zwischen diesen ist wie folgt:<\/p>\n

\\(LOGSPACE\\subseteq P\\subseteq PSPACE\\)<\/blockquote>\n

und<\/p>\n

\\(LOGSPACE\\subsetneqq PSPACE\\).<\/p><\/blockquote>\n

Warum das so ist, wird klar wenn man sich die Definition der 4 Komplexit\u00e4tsklassen anschaut und sich die Beziehungen vor Augen f\u00fchrt:<\/p>\n

In \\(PSPACE\\) sind alle Bandkomplexit\u00e4tsklassen drin, die maximal einen polynomialen Bandbedarf haben. Dass \\(LOGSPACE\\) eine echte Teilmenge<\/strong> davon ist (Unterschied zwischen Teilmenge und echte Teilmenge klar?), sollte einleuchten (logarithmischer Platzbedarf ist zwar ein Teil, aber sicher kleiner als polynomialer Platzbedarf. Daher auch echte Teilmenge<\/strong> und nicht nur Teilmenge). Damit haben wir schon einmal \\(LOGSPACE\\subsetneqq PSPACE\\) erkl\u00e4rt.<\/p>\n

Durch den Satz aus Kurseinheit 1<\/a>:<\/p>\n

\\((1)\\) Sei \\(f:\\mathbb{N}\\rightarrow\\mathbb{N}\\). Dann gilt:  \\(ZEIT(f)\\subseteq BAND(f)\\)<\/p>\n

\\((1)\\) Sei \\(log\\in O(f)\\). Dann ist \\(BAND(f)\\subseteq \\bigcup_{c\\in\\mathbb{N}} ZEIT(c^{f(n)})\\)<\/p><\/blockquote>\n

haben wir auch unsere Beziehung zwischen \\(LOGSPACE\\), \\(PSPACE\\) und \\(P\\) hergestellt.<\/p>\n

Um \\((1)\\) und \\((2)\\) nachzuvollziehen m\u00fcssen wir uns nur noch einmal daran erinnern, dass der Platzbedarf nie gr\u00f6\u00dfer sein kann als die die Anzahl der maximalen Schritte, die eine Maschine tun kann. Denn in jedem Schritt k\u00f6nnen wir nur ein Feld beschreiben. Wir beschr\u00e4nken so nicht nur die Maschine, sondern auch ihren Bandverbrauch.<\/p>\n

Damit ist \\(LOGSPACE\\subseteq{P}\\subseteq PSPACE\\).<\/p>\n

Wo ist \\(LOGTIME\\)? Diese Klasse ist nicht sonderlich spannend, wenn auch vorhanden. In \\(LOGTIME\\) liegt z.B. das Nachschauen in einer sortierten Liste. Wir schauen uns die nicht komplett an, sondern gucken nach einem Element, welches sich irgendwo befinden kann. Die bin\u00e4re Suche<\/a> ist ein prominenter Vertreter eines Algorithmus in der Komplexit\u00e4tsklasse \\(LOGTIME\\).<\/p>\n

Der Vollst\u00e4ndigkeit halber: die vollst\u00e4ndige Beziehung zwischen den einzelnen Komplexit\u00e4tsklassen <\/a>ist (nichtdeterministische Problemklassen ausgelassen): \\(L\\subseteq P\\subseteq NP\\subseteq PSPACE\\).<\/p>\n

\"ppspace\"<\/a><\/p>\n

Quelle: Wikipedia<\/a><\/p>\n

Antwort zum Lernziel<\/strong>: die Beziehungen zwischen den Klassen erfolgen mittels den Hierarchiese\u00e4tzen f\u00fcr Band und die folgende Teilmengen-Beziehung zwischen Zeit und Band gilt: \\(ZEIT(f)\\subseteq BAND(f)\\). Damit bilden wir eine Hierarchie zwischen \\(LOGSPACE\\), \\(P\\) und \\(PSCAPE\\) hergestellt.<\/p>\n

Wer noch ein paar Details zum Thema \\(P-NP\\) haben m\u00f6chte, der kann sich den folgenden Beitrag<\/a> anschauen und sich schon ein klein wenig auf die nun folgenden Kurseinheiten zu diesem Thema einstimmen.<\/p>\n

Wieder gilt: wer Fehler findet, bitte ASAP in die Kommentare oder per Mail damit falsches Zeug nicht zu lange online steht.<\/p>\n","protected":false},"excerpt":{"rendered":"

Update 4: MathJax wollte nicht so, wie ich oder einige Leser des Blogs. Nun sollten alle Symbole wieder angezeigt werden. Update 3: Ein kleiner Exkurs zum Thema wurde hinzugef\u00fcgt. Update 2: Zwei Fehler in der Berechnung im Lernziel 3 sind nun gefixt. Update: Antworten zu Lernzielen hinzugef\u00fcgt. Soweit m\u00f6glich. Lernziel 1 Verstehen des Verfahrens von … <\/p>\n

\u201eTIB: Separations- und Hierarchies\u00e4tze (Lernziele KE2, Update 2)\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-1390","post","type-post","status-publish","format-standard","hentry","category-theoretische-informatik"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1390","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1390"}],"version-history":[{"count":95,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1390\/revisions"}],"predecessor-version":[{"id":3547,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1390\/revisions\/3547"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1390"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1390"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1390"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}