grundlegende Begriffe, Prinzipien und Methoden aus der Algorithmentheorie und der Komplexitätstheorie
…zu einem tieferen Verständnis praktischer Problemstellungen.
(Quelle: Modulbeschreibung)
was sind Algorithmen?
wie hängen verschiedene Alg.-Definitionen zusammen?
welche Probleme sind algorithmisch lösbar?
…mit welchem Ressourcenverbrauch?
Nein! (Das ist ein wichtiges Resultat und wir sehen eine wichtige Beweismethode.)
wir zählen alle Programmtexte auf (der Größe nach und innerhalb einer Größe lexikografisch), die totale Funktionen \(\mathbb{N}\to\mathbb{N}\) realisieren.
erhalten damit eine unendl. Folge von Funkt. \(f_0, f_1,\ldots\),
jede berechbare Fkt. kommt in dieser Folge vor
(evtl. auch mehrfach, das ist egal)
definiere \(g: \mathbb{N}\to\mathbb{N}: x\mapsto f_x(x)+1\)
Satz: \(g\) ist nicht berechenbar.
Beweis (indirekt): sonst \(\exists i\) mit \(f_i=g\), betrachte \(g(i)\)
\(E_3\): Sprach-Äquivalenz von Typ-3-Grammatiken
\(E_2\): Sprach-Äquivalenz von Typ-2-Grammatiken
gesucht ist jeweils Algorithmus mit dieser Eigenschaft:
Eingabe ist Paar \((G_1,G_2)\) von Grammatiken,
Ausgabe ist 1, falls \(L(G_1)=L(G_2)\), sonst 0
praktische Motivation: Test bzw. Verkleinerung von regulären Ausdrücken, von Grammatiken (automatische Bewertung von Übunsgaufgaben zu AFS!)
\(E_3\) ist entscheidbar, siehe Vorlesung AFS
\(E_2\) nicht entscheidbar! diese Vorlesung (aber nicht heute)
Methode: Reduktion: wenn \(E_2\) entscheidbar, dann auch …
(eine typische Frage der Komplexitätstheorie)
Def. Eine \(k\)-Knoten-Färbung eines Graphen \(G=(V,E)\)
ist Funktion \(f:V\to\{1,2,\dots,k\}\) mit \(\forall uv\in E: f(u)\neq f(v)\).
Def. \(k\text{COL} :=\) die Menge der Graphen,
die eine \(k\)-Knoten-Färbung besitzen.
Probleme:
gegeben \(G\), entscheide \(G\in\text{2COL}\)
gegeben \(G\), entscheide \(G\in\text{3COL}\)
beide Probleme sind entscheidbar (warum?)
für 2COL ist effizienter Algorith. bekannt, für 3COL nicht.
Methode: Reduktion: wenn man 3COL effizient lösen könnte, dann auch …
Berechenbarkeitsmodell \(=\) Programmierparadigma
Registermaschine: imperatives Programmieren
Loop- und While-Programme: strukturiertes (imperat.) P.
primitiv/allgemein-rekursive Funktionen: funktionales P.
(uniforme) Schaltkreise: paralleles Programmieren
nichtdeterministische Maschinen: Suchverfahren
für jede dieser Def.:
exakte Beschreibung (Spezifikation) von (abstrakter) Syntax und Semantik \(=\) Interpreter-Bau
zwischen diesen Def.:
semantik-erhaltende Übersetzung \(=\) Compiler-Bau
Suche nach Lösungsverfahren für mathematische Aufgaben (symbolische Differentiation, Integration, Gleichungssysteme)
Wahrheit einer prädikatenlogischen Formel
das 10. Hilbertsche Problem (1900):
Lösbarkeit von Polynomgleichungen in ganzen Zahlen
…bzw. nach Beweisen für deren Nicht-Existenz
Gödel, Church, Turing (1936,…):
…ist nicht entscheidbar
Matiasevich (1970):
…ist nicht entscheidbar.
(nach K. Wagner: Theor. Inf., Springer 2003)
Die Bedeutung des Algorithmenbegriffs für Mathematik und Informatik entspricht der Bedeutung des Begriffes der natürlichen Zahlen.
Die mathematische Präzisierung des Algorithmenbegriffs und die Erkenntnis der Grenzen des algorithmisch Machbaren gehören zu den wichtigsten intellektuellen Leistungen des 20. Jahrhunderts.
(akt.) Lehrbücher
Juraj Hromkovic: Algorithmische Konzepte der Informatik Teubner 2001
Klaus Wagner: Theoretische Informatik Springer 2003
Ingo Wegener: Theoretische Informatik Teubner 1992
Klassisch:
Hartley Rogers Jr.: Theory of Recursive Functions and Effective Computability, 1987
Michael Garey, David S. Johnson: Computers and Intractability Freeman 1979
wir formalisieren das imperative Programmieren:
Programmtext ist Folge von Befehlen
Programmausführung ist Folge von Zustandsänderungen
Zustand: Speicherbelegung und Befehlsnummer
Eigenschaften dieses Modells:
ist einfach in Hardware realisierbar
(seit Jahrzehten werden Rechner so gebaut)
ist softwaretechnisch unzweckmäßig
(der Beweis für die Korrektheit eines Programms sieht ganz anders aus als das Programm selbst)
Speicher der Maschine besteht aus Registern (Zellen),
Registerinhalte sind aus \(\mathbb{N}\)
Register sind numeriert durch \(\mathbb{N}\)
es werden nur endlich viele Register benutzt
die Menge der möglichen Speicherbelegungen ist
\(S:= \{s \mid s\in(\mathbb{N}\to\mathbb{N}), \{x\mid s(x)\neq 0\} \text{ist endlich} \}\).
Bsp. \(s(0)=42, s(1)=10, \forall x: x\ge 2 \Rightarrow s(x)=0\).
Notation für Speicher-Änderungen: \(s[x:=y]\)
ist die Funktion \(z \mapsto (\text{if~}z=x\text{~then~}y\text{~else~}s(z))\).
Bsp: \(s[1:=8](1)=\dots, s[1:=8](2)=\dots\)
Ü: gilt \(s[a:=b][c:=d] = s[c:=d][a:=b]\) ?
Menge \(B\) der Befehle:
Inc \((\mathbb{N})\), Dec \(\mathbb{N}\), Goto \((\mathbb{N})\), GotoZ \((\mathbb{N}\times\mathbb{N})\), Stop.
Menge \(P\) der Programme \(= B^*\) (Folge von Befehlen)
Bsp. für ein Programm:
[GotoZ 1 5,Dec 1,Inc 0,Inc 0,Goto 0,Stop]
Konfigurationsmenge \(C\subset\mathbb{N}\times S\)
erste Komponente ist Befehlszähler (enthält die Nr. des nächsten auszuführenden Befehls)
Übergangsrelation des Programms \(p\) ist \(\operatorname{step}_p\subseteq C\times C\)
\(((l,s),(l',s'))\in\operatorname{step}_p\), falls \(l < |p|\) und …
wenn \(p_l = \text{Inc}(i)\), dann \(l'=l+1 ,s' = s[i:=s(i)+1]\)
wenn \(p_l = \text{Dec}(i)\), dann …
wenn \(p_l=\text{Goto}(k)\), dann …
wenn \(p_l=\text{GotoZ} (i,k)\), dann:
wenn \(s(i)=0\), dann \(\dots\) sonst \(\dots\)
Satz: Die Relation \(\operatorname{step}_p\) ist eine partielle Funktion.
initiale Konfigur. \(I(x)\) mit Eingabe \(x=(x_1,\ldots,x_n)\in \mathbb{N}^n\):
ist \((0,s)\) mit \(s(1)=x_1,\ldots,s(n)=x_n, s(i)=0\) sonst
finale Konfiguration
\((l,s)\), wobei \(l<|p| \wedge p_l=\text{Stop}\)
die Ausgabe \(O(l,s)\) einer Konfiguration ist \(s(0)\)
Programm \(P\) berechnet die partielle Funktion \(f:\mathbb{N}^n\hookrightarrow \mathbb{N}\).
Es gilt \((x,y) \in f\) gdw.
\((I(x),F) \in\operatorname{step}_p^*\) und \(F\) ist final und \(y=O(F)\)
Jede solche part. Fkt. nennen wir Goto-berechenbar
Die Menge dieser Fkt. nennen wir GOTO
Ü: ein \(p\), das die Funktion \(b(x_1)=42\) berechnet?
Ü: die Semantik des leeren Programms (mit \(|p|=0\)) ist?
[GotoZ 1 5,Dec 1,Inc 0,Inc 0,Goto 0,Stop]
wirklich? glauben wir das? nein. wir beweisen:
das Programm hält für jede Eingabe (vgl. Def. \(\operatorname{step}_p^*\))
die Ausgabe ist korrekt
wir ordnen jeder Konfiguration \((l,s)\) zu:
die Invariante \(s(0)+2\cdot s(1)\)
die Schranke \(s(1)\)
und zeigen (für die Teilfolge aller Konfig. mit \(l=0\)):
die Invariante ist: 1. anfangs wahr, 2. invariant,
3. schließlich nützlich.
die Schranke nimmt ab (um wieviel?) und bleibt \(\ge 0\).
diese Funktionen sind goto-berechenbar:
jede konstante Funktion
die identische Funktion
jede Projektion \((x_1,\ldots, x_n)\mapsto x_k\)
die Addition
die schwache Subtraktion \((x_1,x_2)\mapsto\max(0,x_1-x_2)\), Notation: \(x_1\dotdiv x_2\)
wenn \(f:\mathbb{N}\to\mathbb{N}\) und \(g:\mathbb{N}\to\mathbb{N}\) goto-berechenbar sind,
dann auch \(x\mapsto f(g(x))\).
Beweis:
Programm für \(g\); \(R_1:=R_0; R_0 := 0\); Programm für \(f\).
Ü: warum \(R_0 := 0\)?
wenn \(f:\mathbb{N}^2 \to\mathbb{N},g_1,g_2:\mathbb{N}\to\mathbb{N}\) goto-berechenbar sind,
dann auch \(x\mapsto f(g_1(x),g_2(x))\).
einfach Programm für \(g_1\), Programm für \(g_2\), …? Nein.
formalisiert maschinennahe imperative Programmierung
(Programmausführung als Folge von Speicherzustandsänderungen)
der Befehlssatz ist klein, die Ausdruckskraft scheint gering, aber immerhin …
gewisse einfache Funktionen sind in GOTO
GOTO ist abgeschlossen bzgl. gewisser Operatoren
später werden wir sehen
die Ausdruckskraft ist tatsächlich sehr hoch,
GOTO \(=\) Java-berechenbar \(=\) …
GOTO-Programme für elementare Funktionen: in Olat/Autotool ausprobieren. (Ggf. Highscore-Wertung für kurze Programme.)
Ü: gilt \(s[a:=b][c:=d] = s[c:=d][a:=b]\) ?
Beweisen Sie: die Relation \(\operatorname{step}_p^*\cap \{(C_1,C_2)\mid C_2 \text{ist final}\}\) ist eine partielle Funktion.
(Dabei Wdhlg. Begriffe und Notation für Relationen und partielle Funktionen.)
Sei \(A\) die Menge der partiellen Fkt., die durch ein Goto-Programm berechnet werden können, in dem der Befehl Goto nicht vorkommt. Beweisen Sie \(\text{GOTO} = A\).
Das sind zwei Inklusionen, die eine ist trivial, für die andere übersetzen Sie einen unbedingten in einen bedingten Sprung.
Sei \(B\) die Menge der partiellen Fkt., die durch ein Goto-Programm berechnet werden können, in dem der Befehl GotoZ nicht vorkommt (m.a.W., nur unbedingte Sprünge),
Geben Sie ein Verfahren an, das entscheidet, ob ein \(B\)-Programm eine totale Funktion berechnet.
Sei \(C\) die Menge der partielle Ftk., die durch ein Goto-Programm berechnet werden können, in dem weder Goto noch GotoZ vorkommen (m.a.W., die Geradeaus-Programme).
Welche Geradeaus-Programme berechnen totale Funktionen?
Beweisen Sie \(B=C\). (zwei Inklusionen, d.h. zwei Compiler)
Goto-Programme sind flach (Listen von Befehlen), haben keine sichtbare Struktur. Das ist gut für die Hardware, schlecht für den Programmierer.
Struktur \(=\) Hierarchie \(=\) Bäume.
Programme sind ab jetzt Bäume. (entspricht etwa dem Schritt von Assembler/Fortran zu Algol, \(\approx\) 1960)
NB: Das ist immer noch imperative Programmierung, deswegen immer noch schlecht für den Programmierer (weil die Semantikdefinition einen Maschinenzustand benutzt, den man im Programm nicht sieht).
Ausweg: funktionale Programmierung (kein Zustand).
Menge der While-Programme \(P\)
elementare: \(\operatorname{\textsf{Inc}}\mathbb{N}\), \(\operatorname{\textsf{Dec}}\mathbb{N}\), leeres Programm: \(\operatorname{\textsf{Skip}}\)
zusammengesetzte:
Nacheinander: \(\operatorname{\textsf{Seq}}(P\times P)\)
Verzweigung: \(\operatorname{\textsf{IfZ}}(\mathbb{N}\times P\times P)\)
Schleife: \(\operatorname{\textsf{While}}(\mathbb{N}\times P)\)
(kein Stop, kein Goto)
Beispiel:
\(\operatorname{\textsf{While}}(1,\operatorname{\textsf{Seq}}(\operatorname{\textsf{Dec}}(1),\operatorname{\textsf{Inc}}(0)))\).
autotool-Syntax: While 1 (Seq (Dec 1) (Inc 0))
Semantik eines Programms \(p\in P\)
ist Relation (genauer: partielle Funktion) \(\operatorname{sem}_p\subseteq S\times S\) auf Speicherbelegungen.
das ist big step semantics (ein Schritt!)
beachte: es gibt keinen program counter, diese Rolle übernimmt der Index \(p\).
Semantik für elementare Programme: \(\operatorname{sem}_p(s_1,s_2)=\)
\(p=\operatorname{\textsf{Skip}}\wedge s_1=s_2\)
oder \(p=\operatorname{\textsf{Inc}}(i) \wedge s_2=s_1[i:=s_1(i)+1]\)
oder \(p=\operatorname{\textsf{Dec}}(i) \wedge s_2=s_1[i:=\max(0,s_1(i)-1)]\)
oder …(nächste Folie)
\(\operatorname{sem}_p(s_1,s_2) = \dots\)
oder \(p=\operatorname{\textsf{Seq}}(p_1,p_2) \wedge\) \(\exists s': \operatorname{sem}_{p_1}(s_1,s')\wedge\operatorname{sem}_{p_2}(s',s_2)\).
oder \(p=\operatorname{\textsf{IfZ}}(i,p_1,p_2) \wedge\)
(\(s_1(i)=0 \wedge \operatorname{sem}_{p_1}(s_1,s_2)\) oder \(s_1(i)>0 \wedge \operatorname{sem}_{p_2}(s_1,s_2)\))
oder \(p=\operatorname{\textsf{While}}(i,q) \wedge\)
(\(s_1(i)=0 \wedge s_1=s_2\) oder \(s_1(i)>0\wedge \operatorname{sem}_{\operatorname{\textsf{Seq}}(q,p)}(s_1,s_2)\))
Notation \(p\cong q \iff \operatorname{sem}_p=\operatorname{sem}_q\). — Ü: Satz
\(\operatorname{\textsf{Seq}}(\operatorname{\textsf{Skip}},p) \cong p \cong \operatorname{\textsf{Seq}}(p,\operatorname{\textsf{Skip}})\)
\(\operatorname{\textsf{Seq}}(\operatorname{\textsf{Seq}}(p,q),r) \cong \operatorname{\textsf{Seq}}(p,\operatorname{\textsf{Seq}}(q,r))\)
\(\operatorname{\textsf{While}}(i,p)\cong \operatorname{\textsf{IfZ}}(i,\operatorname{\textsf{Skip}},\operatorname{\textsf{Seq}}(p,\operatorname{\textsf{While}}(i,p)))\)
Ü: \(\operatorname{\textsf{IfZ}}\) wird gar nicht benötigt, da man es simulieren kann.
initiale Speicherbelegung \(I(x)\) für Eingabe \(x\in\mathbb{N}^n\):
\(s(i)=\) wenn \(1\le i\le n\), dann \(x_i\), sonst \(0\).
Programm \(p\) berechnet partielle Funktion \(f:\mathbb{N}^n\hookrightarrow \mathbb{N}:\)
\(\forall x\in\mathbb{N}^n: f(x)=y \iff\exists s: \operatorname{sem}_p(I(x),s) \wedge y=s(0)\).
jede so berechenbare partielle Fkt. heißt While-berechenbar.
Übungsaufgaben:
die üblichen elementaren Funktionen sind \(\in\operatorname{\textsf{WHILE}}\)
\(\operatorname{\textsf{WHILE}}\) ist abgeschlossen unter Substitution
Bsp: \(f,g\in\operatorname{\textsf{WHILE}}\Rightarrow (x\mapsto f(g(x))\in\operatorname{\textsf{WHILE}}\)
Interpreter realisiert Semantik. Echter autotool-Quelltext:
https://gitlab.imn.htwk-leipzig.de/autotool/all0/blob/master/collection/src/While/Step.hs
Konfiguration \(c=(t,m)\) enthält
\(t\) (todo): Liste (Keller) von Programmen
\(m\) (memory): Speicherbelegung
mit der Bedeutung: wenn \(t=[p_1,\ldots,p_n]\), dann ist \(S(t):=\operatorname{\textsf{Seq}}(p_1,\ldots,\operatorname{\textsf{Seq}}(p_n,\operatorname{\textsf{Skip}})\dots)\) noch auszuführen.
Relation (small-step semantics) \(\to\) auf Konfigurationen.
Spezifikation (Korrektheit): \(\operatorname{sem}_{S(t)}(i,f) \iff\) \(\left(|t|=0\wedge i=f\right) \vee \left(\exists t', m: (t,i)\to(t',m) \wedge \operatorname{sem}_{S(t')}(m,f) \right)\)
es soll gelten: Satz: \(\operatorname{sem}_p(i,f)\iff ([p],i)\to^*([],f)\)
Satz (Ziel): für jede part. Fkt. \(f\) gilt:
\(f\) ist while-berechenbar \(\iff\) \(f\) ist goto-berechenbar.
äquivalent, kürzer: \(\operatorname{\textsf{WHILE}}=\operatorname{\textsf{GOTO}}\)
praktisches Argument für \(\Rightarrow\): das macht jeder Compiler (etwa von C nach Assembler/Maschinensprache)
Beweis (Ideen): folgen.
(Wenn man das genau macht, dann heißt die Vorlesung Compilerbau)
wir schreiben den Übersetzer:
\(\operatorname{\textsf{compile}}:\mathbb{N}\times\operatorname{\textsf{WHILE}}\to \mathbb{N}\times \operatorname{\textsf{GOTO}}\)
wobei \(\operatorname{\textsf{compile}}(a,p)=(e,q)\) bedeutet:
das Programm \(p\in\operatorname{\textsf{WHILE}}\) wird übersetzt
in ein äquivalentes Programm \(q\in\operatorname{\textsf{GOTO}}\),
das auf Adresse \(a\) beginnt
und auf \(e-1\) endet (d.h. \(e=a+|q|\))
dabei bedeutet Äquivalenz:
\(\forall p\in\operatorname{\textsf{WHILE}},a\in\mathbb{N}:\) sei \((e,q)=\operatorname{\textsf{compile}}(a,p)\),
dann \(\forall s_1,s_2: \operatorname{sem}_p(s_1,s_2) \iff \operatorname{step}_q^*((a,s_1),(e,s_2))\)
einfache Programme:
\(\operatorname{\textsf{compile}}(a,\operatorname{\textsf{Skip}})=(a,[])\)
\(\operatorname{\textsf{compile}}(a,\operatorname{\textsf{Inc}}(i))=(a+1,[\operatorname{\textsf{Inc}}(i)])\).
\(\operatorname{\textsf{compile}}(a,\operatorname{\textsf{Dec}}(i))=(a+1,[\operatorname{\textsf{Dec}}(i)])\).
zusammengesetzte:
\(\operatorname{\textsf{compile}}(a,\operatorname{\textsf{Seq}}(p_1,p_2)) =\)
sei \((m,q_1)=\operatorname{\textsf{compile}}(a,p_1)\) und \((e,q_2)=\operatorname{\textsf{compile}}(m,p_2)\),
dann \((e,q_1\circ q_2)\).
Ansatz:
compile (_, IfZ i p1 p2) =>
A: GotoZ i M
compile (_, p2) ;
Goto E ;
M: compile (_, p1);
E:
Realisierung:
compile (a, IfZ i p1 p2) =
let (h,q2) = compile (a+1,p2)
(e,q1) = compile (h+1,p1)
in (e, [GotoZ i (h+1)] ++ q2
++ [Goto e] ++ q1)
Ansatz:
compile (_, While i p) =>
A: GotoZ i E
compile (_, p) ;
Goto A ;
E:
Realisierung:
compile (a, While i p) =
let (h,q) = compile (a+1,p)
e = h+1
in (e, [GotoZ i e] ++ q ++ [Goto a]
Satz: Für jedes While-Programm \(p\) existiert ein Goto-Programm \(q\), das dieselbe partielle Funktion berechnet wie \(p\).
(äquivalente Formulierung: \(\operatorname{\textsf{WHILE}}\subseteq\operatorname{\textsf{GOTO}}\))
Beweis(plan):
\(q=\operatorname{\textsf{compile}}(0,p) \circ[\operatorname{\textsf{Stop}}]\)
Aussage folgt aus Korrektheit bzgl. der Spezifikation
\(\forall p\in\operatorname{\textsf{WHILE}},a\in\mathbb{N}:\) sei \((e,q)=\operatorname{\textsf{compile}}(a,p)\),
dann \(\forall s_1,s_2: \operatorname{sem}_p(s_1,s_2) \iff \operatorname{step}_q^*((a,s_1),(e,s_2))\)
https://gitlab.imn.htwk-leipzig.de/autotool/all0/blob/master/collection/src/Compiler/While_Goto.hs
das scheint schwieriger:
goto-Programm \(=\) Spaghetti-Code,
while-Programm \(=\) strukturierter Code.
Es geht aber, und das erzeugte While-programm hat eine ganz besondere (einfache) Struktur, die später noch ausgenutzt wird (Kleene-Normalform-Thm)
Eingabe: goto-Programm \(p\),
Ausgabe: äquivalentes While-program \(q\)
bestimme \(c=\) das erste in \(p\) nicht benutzte Register, das verwenden wir als PC. Das nächste Register \(h\) verwenden wir zum Anhalten.
Struktur von \(q\) ist:
Inc h;
While (h) {
if (c == 0) { ... } else {
if (c == 1) { ... } else {
if (c == 2) { ... } else {
.. else Skip
}
für Befehl \(p_i\) erzeuge: if (c==i) q_i else
mit \(q_i=\)
wenn \(p_i\in\{\operatorname{\textsf{Inc}}r,\operatorname{\textsf{Dec}}r\}\), dann \([p_i , \operatorname{\textsf{Inc}}c]\)
wenn \(p_i=\operatorname{\textsf{Stop}}\), dann \([\operatorname{\textsf{Dec}}h]\)
wenn \(p_i=\operatorname{\textsf{Goto}}(l)\), dann \([c:=l]\),
wenn \(p_i=\operatorname{\textsf{GotoZ}}(r, l)\), dann IfZ r (c := l) (Inc c)
Ü: zeige: \(p\) erreicht \(\operatorname{\textsf{Stop}}\) \(\iff\) \(q\) hält.
beachte dabei auch den Fall \(\operatorname{\textsf{Goto}}l\) mit \(l\ge |p|\)
Ü: hier wird if(c==i)
und \(c:=l\) benutzt,
das kann man jeweils mit While implementieren,
geht hier aber auch ohne Schleife, warum?
https://gitlab.imn.htwk-leipzig.de/autotool/all0/blob/master/collection/src/Compiler/Goto_While.hs
Vorige Konstruktion zeigt den Satz:
zu jedem Goto-Programm gibt es ein äquivalentes While-programm (\(\operatorname{\textsf{GOTO}}\subseteq\operatorname{\textsf{WHILE}}\))
mit genau einem While.
zusammen mit \(\operatorname{\textsf{WHILE}}\subseteq\operatorname{\textsf{GOTO}}\) folgt
\(\operatorname{\textsf{WHILE}}=\operatorname{\textsf{GOTO}}\)
zu jedem While-Programm gibt es ein äquivalentes While-Programm mit genau einem While.
äquivalent\(=\) berechnet dieselbe partielle Funktion.
Ü: wie unterscheiden sich die Laufzeiten?
\(\operatorname{\textsf{While}}(i,q)\) bedeutet: solange \(s(i)>0\) ist, \(q\) ausführen
es gibt While-Programme, die nicht für jede Eingabe terminieren (es gibt \(f\in\operatorname{\textsf{WHILE}}\) mit \(f\) nicht total)
\(\operatorname{\textsf{Loop}}(i,q)\) bedeutet: \(q\) genau \(s(i)\) mal ausführen
(der Wert von \(i\) vor Beginn der Schleife)
Loop-Programme terminieren (jede \(f\in\operatorname{\textsf{LOOP}}\) ist total)
das ist softwaretechnisch nützlich
aber auch eine Einschränkung:
es gibt \(f\in(\operatorname{\textsf{WHILE}}\cap\operatorname{\textsf{TOTAL}}) \setminus\operatorname{\textsf{LOOP}}\)
Syntax und Semantik wie While-Programme, außer:
(Syntax) kein While(i,q)
, sondern Loop(i,q)
(Semantik) wenn \(p=\operatorname{\textsf{Loop}}(i,q)\), dann \(\operatorname{sem}_p(s_1,s_2) = \operatorname{sem}_q^{s_1(i)}(s_1,s_2)\)
der Befehl \(q\) wird genau \(s_1(i)\) mal ausgeführt (der Wert von \(i\), wenn die Schleife zu erstenmal betreten wird — egal, was später mit \(i\) passiert)
Jede so berechenbare Fkt. heißt loop-berechenbar.
Die Menge der loop-berechenbaren Fkt. heißt \(\operatorname{\textsf{LOOP}}\).
Bsp: Addition, Subtraktion, Multiplikation, Potenz,
\(n\mapsto n\) ist gerade, \(n\mapsto n\) ist Quadratzahl, \(n\mapsto n\) ist prim,…
bei Loop(i,q)
wird \(q\) genau \(s_1(i)\)-mal durchlaufen
so realisiert in der Sprache Ada (http://www.adaic.org/resources/add_content/standards/12rm/html/RM-5-5.html)
A loop parameter is a constant; it cannot be updated…
for X in 0 .. 10 loop P; end loop;
Iteration (Induktion) über (Peano-)Zahlen (Strichlisten)
verallgemeinert auf andere (strukturierte) Datentypen: Rekursiosmuster (fold
), Entwurfsmuster Iterator
(besucht jedes Element genau einmal)
Java: for (E x : c) { .. }
, C#: foreach
\(\operatorname{\textsf{LOOP}}\subseteq\operatorname{\textsf{WHILE}}\cap\operatorname{\textsf{TOTAL}}\) (Beweis: Übung)
\(\operatorname{\textsf{WHILE}}\cap\operatorname{\textsf{TOTAL}}\not\subseteq\operatorname{\textsf{LOOP}}\). Beweis:
\(L_0,L_1,\dots\) längen-lexikografische Aufzählung aller LOOP-Programme, die einstellige Fkt. berechnen,
diese Fkt. sind \(f_0,f_1,\ldots\)
für \(d: x\mapsto f_x(x)+1\) gilt: \(d\in\operatorname{\textsf{WHILE}}\cap\operatorname{\textsf{TOTAL}}\)
Begründung: Interpreter für LOOP-Programme
dieses \(d\) hat keinen \(L\)-Index (also \(d\notin\operatorname{\textsf{LOOP}}\))
Begründung: falls doch \(d = f_i\), dann betrachte \(d(i)\).
eine arithmetische Funktion \(f \in\operatorname{\textsf{WHILE}}\cap\operatorname{\textsf{TOTAL}}\setminus \operatorname{\textsf{LOOP}}\): die Ackermann-Funktion
\(A:\mathbb{N}^2\to\mathbb{N}\)
\(A(0,y)=y+1; A(x+1,0)=A(x,1);\)
\(A(x+1,y+1)=A(x,A(x+1,y))\)
bestimme \(A(2,4), A(3,3), A(4,2)\)
Satz: \(\forall f\in\operatorname{\textsf{LOOP}}\exists x: \forall \vec{y}: f(\vec{y})\le A(x,\max_i\vec{y}_i)\)
folgt aus
Lemma: (Bezeichnung \(\max s := \max\{s(i)\mid i\in\mathbb{N}\}\) )
\(\forall p\in\operatorname{\textsf{LOOP}}\exists x: \forall (s_1,s_2)\in\operatorname{sem}_p: A(x,\max s_1)\ge \max s_2\)
Beweis durch Induktion über Programmtexte
(…, die im Beweis des Lemmas benötigt werden)
für \(p=\operatorname{\textsf{Inc}}(i)\): (Übung)
für \(p=\operatorname{\textsf{Seq}}(p_1,p_2)\) betrachte Zustände \(s_1\stackrel{\operatorname{sem}_{p_1}}{\longrightarrow} s' \stackrel{\operatorname{sem}_{p_2}}{\longrightarrow} s_2\)
und nach Induktion \(A(x_1,m_1)\ge m', A(x_2,m')\ge m_2\).
Gesucht ist für jedes \(x_1,x_2\)
ein \(x\) mit \(\forall y: A(x,y)\ge A(x_1,A(x_2,y))\).
Wir können \(x=x_1+x_2+2\) wählen
(Beweis: Übung. Benötigt \(A(x,y+1)\le A(x+1,y)\))
für \(p=\operatorname{\textsf{Loop}}(i,q)\): Welche Eigenschaft wird benötigt? (Ü)
Aufgaben zu While- und Loop-Programmen in autotool
Sei \(W_{\textsf{Syn}}\) die Menge der While-Programme, in denen \(\operatorname{\textsf{IfZ}}\) nicht vorkommt, und \(W_{\textsf{Sem}}\) die Menge der durch solche Programme berechenbaren partiellen Funktionen.
Zeigen Sie \(W_{\textsf{Sem}}=\operatorname{\textsf{WHILE}}\).
Zeigen Sie für einstellige partielle Funktionen:
\(f,g\in\operatorname{\textsf{WHILE}}\Rightarrow (x\mapsto f(g(x)))\in\operatorname{\textsf{WHILE}}\).
Zur Kompilation von Goto nach While:
Zeigen Sie: \(p\) erreicht Stop \(\iff\) \(q\) hält
Es werden if (c==i)
und c := l
benutzt, das kann man im Allgemeinen mit While implementieren (wie?) geht aber hier auch ohne Schleife (wie?)
Vergleichen Sie die Laufzeiten von \(p\) und \(q\).
zur Ackermann-Funktion:
Bestimmen Sie \(A(2,4),A(3,3),A(4,2)\)
Aufgaben auf Folie Eigensch. Ackermann
In vielen Anwendungen sind Daten strukturiert (z.B. Tupel, Listen, Bäume). Goto-Programme rechnen aber nur mit Zahlen.
Satz: Das ist keine Einschränkung der Allgemeinheit, denn man kann jedes strukturierte Datum in eine einzige (mglw. große) Zahl kodieren.
wird Gödelisierung genannt (Kurt Gödel, 1906–1978)
anschauliches Argument: der Speicherinhalt eines PC ist eine Bitfolge, die kann man als Binärdarstellung einer Zahl auffassen. — exakte Argumente: folgen.
gesucht sind (goto-berechenbare) Funktionen
Konstruktor: \(C:\mathbb{N}^2\to \mathbb{N}\) Destruktoren: \(P_1,P_2:\mathbb{N}\to\mathbb{N}\)
Testfunktion: \(T:\mathbb{N}\to\{0,1\}\)
mit Spezifikation (vgl. objektorientierte Datenmodellierung)
\(\forall x_1,x_2: P_1(C(x_1,x_2))=x_1\wedge P_2(C(x_1,x_2)) = x_2\)
\(\forall x: T(x)=1 \iff \exists x_1,x_2: x=C(x_1,x_2)\)
da gibt es viele verschiedene Möglichkeiten
\(C(x_1,x_2)= (x_1+x_2)(x_1+x_2+1)/2 + x_1\)
\(C(x_1,x_2)=2^{x_1}(2x_2+1)\), \(\bullet\) \(C(x_1,x_2)=2^{x_1}\cdot 3^{x_2}\)
Ü: jeweils \(C(2,3), C(3,2), T(10), T(12), P_1(12),P_2(12)\),
Algorithmen (Loop-Programme) für \(T, P_i\).
Kostruktor: \(L:\mathbb{N}^*\to \mathbb{N}\), Destruktoren \(D_i:\mathbb{N}^*\hookrightarrow \mathbb{N}\).
zwei (von vielen) Möglichkeiten:
mittels einer Paar-Kodierung \(C\)
L (l) = if null l then 0
else 1 + C (head l, L (tail l))
direkte Kodierung als Produkt von Primzahlpotenzen \(L([x_0,x_2,\ldots, x_n]) = 2^{x_0+1}\cdot 3^{x_1+1}\cdot \dots \cdot p(n)^{x_n+1}\).
Ü: jeweils \(L([]), L([5]), L([2,3,0])\), Algorithmus für \(D_i\)
Ü: die Funktion \(p:n\mapsto\) die \(n\)-te Primzahl, also \(p(0)=2, p(1)=3, p(2)=5,\dots\) ist While-berechenbar.
Ü : \(p\) ist Loop-berechenbar. — Hinweis: Euklid.
Motivation
allgemein: Baum \(=\) Term in einer Signatur,
Signatur: eine endlichen Menge von Funktionssymbolen mit zugeordneter Stelligkeit.
Bsp: \(\Sigma=\{(f,2),(g,1),(a,0)\}\), \(t = f(f(a,g(a)),a)\in\operatorname{Term}(\Sigma)\).
Notation \(\text{root}(t)=f, \text{args}(t)=[f(a,g(a)),a]\).
wird u.a. benötigt, um (prädikatenlogische) Formeln als Zahlen zu kodieren.
Realisierung: \(B(t) = C(\text{num}(\text{root}(t)), L([B(t_1),\ldots,B(t_k)]))\)
mit \(\text{args}(t)=[t_1,\ldots]\), Paar-Kodierung \(C\),
Listen-Kodierung \(L\), sowie Symbol-Numerierung
Ü: Kodierung für endliche Mengen von Zahlen
man kann mit eben gezeigten Methoden nach \(\mathbb{N}\) kodieren:
Goto-Programme
(Programm ist Liste von Befehlen, Befehl ist Tupel)
Maschinen-Konfigurationen
(Paar von Zahl und Speicherbelegung, diese ist Liste (!))
Damit kann man in der Sprache GOTO
einen Interpreter für GOTO-Programme schreiben.
Insbesondere sind für jedes \(p\) die Übergangsfunktion \(\operatorname{step}_p\) sowie ihre transitive reflexive Hülle goto-berechenbar (nach Kodierung):
bei Eingabe einer Kodierung von \(p\) und einer Konfig. \(K\) kann die Folgekonfiguration berechnet werden und dies solange wiederholt werden, bis finale Konf. erreicht wird.
D.h. die part. Funktion \(\phi:\mathbb{N}^2\hookrightarrow\mathbb{N}\) ist goto-berechenbar: \(\phi_x(y)=\) die Ausgabe einer Maschine, die das Programm mit Kodierung \(x\) auf Eingabe mit Kodierung \(y\) ausführt.
Das Programm für \(\phi\) heißt universell, denn es kann die Rechnung jedes Goto-Programms simulieren.
Def: das (spezielle) Halteproblem ist die Menge \(K_0 = \{ x \mid \phi_x(x)\downarrow \}\subseteq\mathbb{N}\).
(die Menge der Kodierungen von Programmen, die anhalten, wenn man sie auf sich selbst, d.h. ihren eigenen Code, anwendet).
Satz: die charakteristische Funktion \(c_{K_0}:\mathbb{N}\to\{0,1\}\) der Menge \(K_0\) ist nicht goto-berechenbar.
Beweis (indirekt): falls doch, dann gibt es ein Programm, das \(c_{K_0}\) berechnet. Es gibt dann auch ein Programm
\(x\mapsto\) wenn \(c_{K_0}(x)=0\), dann 1, sonst \(\bot\) (eine nicht haltende Rechnung).
Sei \(q\) der Code dieses Programms. Ist \(q \in K_0\)? Gdw. \(\phi_q(q)\downarrow\), gdw. \(c_{K_0}(q)=0\), gdw. \(q\notin K_0\).
Satz: es gibt Funktionen \(\mathbb{N}\to\mathbb{N}\), die durch kein goto-Programm berechenbar sind.
Beweise: \(c_{K_0}\)
Def: das (allgemeine) Halteproblem ist die Menge \(K=\{ C(x,y) \mid \phi_x(y)\downarrow \}\).
Satz: charakterist. Funkt. \(c_K\) ist nicht goto-berechenbar.
Beweis: sonst könnte man auch \(c_{K_0}\) berechnen.
Es gibt also kein allgemeines Verfahren, mit dem man entscheiden kann, ob ein Programm für eine Eingabe nach endlich vielen Schritten hält.
schon zweimal benutzt, und kommt noch öfter:
für eine Menge \(F\) von Funktionen
gibt es eine Aufzählung \(f_0, f_1, f_2\ldots\)
konstruiere \(g: x \mapsto\) geeignete Änderung von \(f_x(x)\),
so daß \(g\) in Aufzählung nicht vorkommt (\(\neg\exists i: g=f_i\))
Anwendungen bisher:
\(F =\) die totalen berechenbaren Funktionen
\(\Rightarrow\) es gibt totale nicht berechenbare Fkt.
\(F =\) die partiellen berechenbaren Funktionen
\(\Rightarrow\) das Halteproblem ist nicht entscheidbar
wir haben gezeigt: \(\operatorname{\textsf{GOTO}}= \operatorname{\textsf{WHILE}}\)
die Syntax und Semantik (Interpreter) waren jeweils spezifisch, aber wir haben Compiler konstruiert
Verallgemeinerung (Alonzo Church, Alan Turing)
alle vernünftigen Berechenbarkeitsmodelle definieren die gleiche Klasse von partiellen Funktionen
weitere Modelle: Wortersetzung (Turing-Maschinen), funktionale Programmierung (rekursive Fkt.)
\(f:\mathbb{N}^*\hookrightarrow \mathbb{N}\) ist partiell-rekursiv, \(f\in\operatorname{\text{Part}}\):
\(f\) ist While-berechenbar (\(=\) Goto-berechenbar
\(=\) Turing-berechenbar \(=\) …-berechenbar \(=\) …)
\(f:\mathbb{N}^*\hookrightarrow\mathbb{N}\) ist allgemein-rekursiv, \(f \in \operatorname{\text{Allg}}\):
\(f\) ist partiell rekursiv und total.
\(f:\mathbb{N}^* \to \mathbb{N}\) ist primitiv-rekursiv, \(f\in\operatorname{\text{Prim}}\):
\(f\) ist Loop-berechenbar (\(=\) …)
Begründung:
While-Schleife \(\iff\) beliebige Rekursion
Loop-Schleife \(\iff\) eingeschränkte (primitive) Rekursion
alle intuitiv vernünftigen Berechenbarkeitsmodelle definieren die gleiche Klasse von partiellen Funktionen
ein Berechnungsmodell ist gegeben durch
eine Tupel-Kodierung \(C\)
eine universelle Funktion (Interpreter) \(\phi:\mathbb{N}\times\mathbb{N}\hookrightarrow\mathbb{N}\)
und bestimmt Menge von in diesem Modell berechenbaren partiellen Funktionen \(M = \{ \vec{x}\mapsto \phi_p(C(\vec{x})) \mid p\in\mathbb{N}\} \subseteq (\mathbb{N}^*\hookrightarrow \mathbb{N})\)
Die C-T-These kann man auffassen als empirische Aussage oder als Definition (\(M\) ist vernünftig \(\iff\) es gibt beide Compiler \(M \leftrightarrow \operatorname{\textsf{WHILE}}\))
Satz (Stephen Kleene, 1938): Sei \(f\) total und berechenbar.
Dann gibt es ein \(i\) mit \(\phi_i = \phi_{f(i)}\).
Beweis:
bestimme \(h\), so daß \(h(x)\) ein Index für diese Funktion ist: \(y \mapsto \phi_{\phi_x(x)}(y)\).
Bestimme \(e\) als einen Index für \(x \mapsto f(h(x))\).
Das gesuchte \(i\) ist \(h(e)\).
Ü: wende Satz an auf die Funktion
\(f: x\mapsto\) ein Index für die konstante Funktion \(y \mapsto x\).
Der Fixpunkt-Index für \(f\) ist (indiziert) ein Programm,
das seinen eigenen Quelltext ausgibt.
Geht in jeder (in unserem Sinne vernünftigen) Sprache!
Satz: jede nichttriviale semantische Eigenschaft von Programmen ist unentscheidbar.
dabei bedeuten:
Eigenschaft: Menge \(E\subseteq\mathbb{N}\) von Gödelnummern
nichttrivial: \(E\neq\emptyset\wedge E\neq\mathbb{N}\)
semantisch: \(\forall x,y: (\phi_x=\phi_y) \Rightarrow (x\in E \iff y\in E)\)
Beispiele (semantisch oder nicht?)
das Programm berechnet eine totale Funktion
\(\{x\mid \dom(\phi_x)=\mathbb{N}\}\)
die Länge des Programmtextes ist eine gerade Zahl
\(\{x\mid \dom(\phi_x)=2\mathbb{N}\}\)
die Gödelnummer ist gerade (\(2\mathbb{N}\))
wähle \(y\in E, n\in\mathbb{N}\setminus E\).
sei \(E\) entscheidbar, d.h., \(c_E\) berechenbar.
Dann ist dieses \(f\) berechenbar und total:
\(f:x\mapsto\) wenn \(c_E(x)=1\), dann \(n\), sonst \(y\).
Nach Konstruktion \(x\in E \iff f(x)\notin E\).
nach Fixpunktsatz gibt es \(x\) mit \(\phi_x=\phi_{f(x)}\).
Damit \(x\in E\iff f(x)\in E\).
vgl. Aufgabe autotool und Übung 5 zu \(B_{\operatorname{\textsf{While}}}\).
ein Programm, das ziemlich lange rechnet:
Seq (Inc 1)
(While 1
(Seq (Inc 1)
(Seq (Inc 1)
(Seq (Inc 1)
(Seq (While 2
(Seq (Dec 2)
(While 1
(Seq (Inc 2)
(Seq (Inc 2) (Dec 1))))))
(Inc 2))))))
für Turingmaschinen:
Heiner Marxen, Jürgen Buntrock, Attacking the Busy Beaver 5, Bulletin of the EATCS, Number 40, February 1990, pp. 247-251 https://www.drb.insel.de/~heiner/BB/
Pascal Michel: Historical Survey of Busy Beavers http://www.logique.jussieu.fr/~michel/ha.html
Beispiel-Rechnungen (siehe Folien) zu Kodierung von Paaren, Listen, Bäumen
für die Primzahlfunktion \(p\) gilt: \(p\in\operatorname{\textsf{LOOP}}\).
Hinweis: \(p\in\operatorname{\textsf{WHILE}}\) ist einfach, man muß jetzt zusätzlich eine Loop-berechenbare obere Schranke für \(p(n)\) angeben. Diese kann großzügig sein, z.B. aus Beweis von Euklid für es gibt unendlich viele Primzahlen.
Def. \(T(x,y,z):=\) die vom Goto-Programm \(x\) bei Eingabe \(y\) nach \(z\) Schritten erreichte Konfiguration.
(genauer: \(x\) ist die Kodierung des Programmtextes, \(y\) ist die Kodierung des Eingabevektors, Ausgabe ist die Kodierung einer Konfiguration oder einer Fehlermeldung, falls Programm schon vorher gehalten hat)
\(T\) ist Loop-berechenbar.
zur Diagonalisierung: wende das Verfahren an auf
\(F=\) alle linearen Funktionen \(x\mapsto ax+b\) mit \(a,b\in\mathbb{N}\), \(g(x)=f_x(x)+1\)
\(F=\) alle Loop-berechenbaren Funktionen, \(g(x)=(f_x(x)+1) \textbf{mod} 2\)
\(F= (\mathbb{N}\to\mathbb{N})\), d.h., alle Funktionen (egal, ob berechenbar), \(g(x)=f_x(x)+1\).
Def. \(B_{\operatorname{\textsf{While}}}(x):=\) die größte Schrittzahl aller bei leerer Eingabe haltenden While-Programme der Größe \(\le x\) (vgl. autotool-Aufgabe).
Beweisen Sie: \({B_{\operatorname{\textsf{While}}}}\) ist nicht berechenbar.
Hinweis: indirekt. Wenn \({B_{\operatorname{\textsf{While}}}}\) berechenbar, dann Halteproblem entscheidbar.
Entspr. \(B_{\operatorname{\textsf{Loop}}}\). Ist \({B_{\operatorname{\textsf{Loop}}}}\in\operatorname{\textsf{WHILE}}\)? Ist \({B_{\operatorname{\textsf{Loop}}}}\in\operatorname{\textsf{LOOP}}\)?
(Ja. Nein. Hinweis: betrachte Loop-Programm für \(f : x\mapsto 1+2\cdot {B_{\operatorname{\textsf{Loop}}}}(x)\), rufe dieses geeignet auf.)
Ü-Aufgabe von Folie Fixpunktsatz.
Geben Sie ein Programm in Java (C, Haskell,…) an,
das seinen eigenen Quelltext ausgibt.
(Nur Schreiben auf Standardausgabe, keine Dateioperationen, d.h., Programm darf seinen Quelltext nicht von externem Speicher holen, sondern muß ihn selbst enthalten oder erzeugen)
Hinweis: (Garry Thompson, 1999) http://www.nyx.net/~gthompso/quine.htm
Beweisen Sie: für jedes \(i\in\mathbb{N}\) gibt es unendlich viele Indizes (die Menge \(E_i:= \{j \mid \phi_i=\phi_j\}\) ist unendlich)
Hinweis: \(j\in E_i\) ist eine semantische Eigenschaft.
allgemeines Ziel ist Einordnung der Schwierigkeit von Entscheidungsproblemen
nach Kodierung: Problem \(=\) Teilmenge \(P\) von \(\mathbb{N}\)
zu entscheiden ist dann, ob \(x\in P\), d.h. \(c_P(x)=1\)
Def: \(\operatorname{REC}= \{ P \mid P\subseteq \mathbb{N}, c_P \text{ist berechenbar}\}\)
(Name kommt von berechenbar durch rekursive Fkt.)
Beispiele: Primzahlen \(\in\operatorname{REC}\), \(K_0\notin \operatorname{REC}\)
konkrete Ziele:
(Abschluß-)Eigenschaften von \(\operatorname{REC}\)
Beweisverfahren für \(P\in\operatorname{REC}, P\notin\operatorname{REC}\)
genauere Struktur für \(2^\mathbb{N}\setminus\operatorname{REC}\)
Satz (\(\operatorname{REC}\) ist abgeschlossen unter Booleschen Operationen):
wenn \(A,B\in \operatorname{REC}\), dann
\(A\cup B \in \operatorname{REC}\)
\(A\cap B \in \operatorname{REC}\)
\((\mathbb{N}\setminus A)\in\operatorname{REC}\)
Beweis (Beispiel):
Wenn \(c_A, c_B\) rekursive Fkt, dann auch \(c_{A\cup B}\):
\(c_{A\cup B}(x)=\max(c_A(x),c_B(x))\),
d.h. \(c_{A\cup B}=\text{SUBST}(\max,c_A,c_B)\).
Zum Vergleich der algorithmischen Schwierigkeit von Probleme definiert man:
\(P\le_m Q\) (\(P\) ist reduzierbar auf \(Q\)) durch:
es existiert eine berechenbare totale Funktion \(f:\mathbb{N}\to\mathbb{N}\) mit \(\forall x\in\mathbb{N}: x\in P\iff f(x)\in Q\).
beachte die Richtung: \(P\) ist höchstens so schwierig wie \(Q\)
reduzieren bedeutet: ein Entscheidungsverfahren für \(P\) auf ein Verfahren für \(Q\) zurückführen.
Index \(m\) kommt von many-one-Reduktion
Satz: \(P\le_m Q\wedge Q\in\operatorname{REC}\Rightarrow P\in\operatorname{REC}\).
Beweis: gegeben \(c_Q\), konstruiere \(c_P=\text{SUBST}(\dots)\)
Satz (Ü): \(\le_m\) ist transitiv
Def (Wdhlg)
das allgemeine Halteproblem, \(K=\{C(x,y)\mid \phi_x(y)\downarrow\}\).
das spezielle Halteproblem, \(K_0=\{x\mid \phi_x(x)\downarrow\}\).
Satz: \(K_0\le_m K\). Beweis: \(x\in K_0\iff C(x,x)\in K\).
Folgerung: wir hatten gezeigt \(K_0\notin\operatorname{REC}\), also gilt \(K\notin\operatorname{REC}\).
Ü: zeige \(K\le_m K_0\).
Wir bezeichen \(T=\{ x \mid \phi_x \text{ist total}\}\).
Satz: \(T\notin\operatorname{REC}\).
Beweis (Ü): zeige \(K\le_m T\).
Betrachte dazu die 3-stellige (!) Fkt \(g:(x,y,z)\mapsto \phi_x(y)\)
und wende \(s^2_1\) an.
\(K_0\notin\operatorname{REC}, T\notin \operatorname{REC}\). Sind beide Probleme gleich schwer?
Nein. \(K_0\) ist rekursiv aufzählbar, \(T\) ist es nicht.
Def. \(P\subseteq\mathbb{N}\) heißt rekursiv aufzählbar, falls \(P=\emptyset\) oder
es gibt totale berechenbare Funktion \(f\) mit \(P=f(\mathbb{N})\).
Im zweiten Fall ist \(P=\{f(0),f(1),f(2),\ldots\}\). — Beachte:
jedes Element von \(P\) kommt wenigstens einmal vor,
\(f\) ist nicht notwendig injektiv (wiederholungsfrei),
\(f\) ist nicht notwendig monoton.
Die Menge der rek. aufzählbaren Mengen heißt \(\operatorname{RE}\).
Ü: \(P\in\operatorname{RE}\wedge \text{\)P\(unendlich}\Rightarrow\) \(P\) ist injektiv aufzählbar
Ü: \(\text{\)P\(unendlich} \wedge\) \(P\) streng monoton aufzählbar \(\Rightarrow\) \(P\in\operatorname{REC}\).
(Wdhlg.) \(P\in\operatorname{RE}\) : \(P=\emptyset\) oder \(\exists f\in\operatorname{\text{Allg}}: P=\rng(f)\)
Satz: \(P\in \operatorname{RE}\iff \exists f\in\operatorname{\text{Part}}: P=\dom(f)\)
Beweis: \(\Rightarrow\). \(P=\emptyset\): \(f\) hält niemals.
\(P\) wird aufgezählt durch \(g\): \(f(x):=\) wenn \(x\) in \(g(0),g(1),\ldots\) vorkommt, dann 1. (sonst hält die Rechnung nicht.)
Beweis: \(\Leftarrow\) trivial für \(P\) endlich.
Tabelle mit \((x,y)\): die Konfiguration nach \(y\) Schritten in der Rechnung \(f(x)\) (oder Markierung, daß schon fertig).
Tabelle gemäß Kodierung von \(\mathbb{N}^2\) durchlaufen.
Wenn Konfiguration \((x,y)\) final, dann \(x\) ausgeben.
Anwendung: \(K_0\in\operatorname{RE}\). Beweis: \(K_0=\dom(x\mapsto \phi_x(x))\).
Bezeichnung (Gödelisierung for \(\operatorname{RE}\)) \(W_x := \dom (\phi_x)\)
Satz (offensichtlich): \(A\in\operatorname{RE}, B\in\operatorname{RE}\Rightarrow (A\cup B)\in\operatorname{RE}\).
Beweis: trivial wenn \(A=\emptyset\) oder \(B=\emptyset\).
Sei \(f\) die aufzählende Funktion für \(A\), \(g\) die für \(B\).
Dann \(h(2n)=f(n), h(2n+1)=g(n)\).
Satz (nicht offensichtlich): \(A\in\operatorname{RE}, B\in\operatorname{RE}\Rightarrow (A\cap B)\in\operatorname{RE}\).
Die Schwierigkeit ist: wenn man ein \(x=f(n)\in A\) hat,
kann man nicht ausrechen, ob \(x\in B\),
denn möglicherweise ist \(B\notin\operatorname{REC}\).
Beweis: 2-dim. unendliche Tabelle,
In Zeile \(x\), Spalte \(y\) steht Zahlenpaar \((f(x),g(y))\).
Wenn …, gibt …aus.
Ü: alternativer Beweis über Def.-Bereiche
Satz: \(P\in\operatorname{RE}\wedge (\mathbb{N}\setminus P)\in\operatorname{RE} \iff P\in\operatorname{REC}\)
Beweis: \(\Leftarrow\) als Ü. – Für \(\Rightarrow\):
trivial, wenn \(P=\emptyset\) oder \(P=\mathbb{N}\). — ansonsten:
Sei \(f\) eine Aufzählung für \(P\), \(g\) eine Aufzählung für \(\mathbb{N}\setminus P\).
um zu bestimmen, ob \(x\in P\):
berechne \(f(0),g(0),f(1),g(1),f(2),\ldots\)
bis \(x\) erscheint
diese Verfahren hält. (Beweis durch Fallunterscheidung.)
Diese Aussage in anderer Bezeichnung:
Def: \(\operatorname{coRE}=\{P \mid (\mathbb{N}\setminus P) \in \operatorname{RE}\}\) Satz: \(\operatorname{RE}\cap\operatorname{coRE}=\operatorname{REC}\).
Folgerung: \((\mathbb{N}\setminus K_0)\notin\operatorname{RE}\).
Satz: \(P\le_mQ \wedge Q\in\operatorname{RE}\Rightarrow P\in\operatorname{RE}\).
Beweis (Variante 1)
\(f\) die Funktion aus der Reduktion \(\le_m\), \(Q=\dom(\phi_i)\).
Dann \(P=\dom(x \mapsto \phi_i(f(x))\).
Beweis (Variante 2 – Übung)
Sei \(g\) die Aufzählung für \(Q\).
(Falls existiert. Sonst \(Q=\emptyset\), was dann?)
Bestimme Aufzählung für \(P\) mit 2-dim unendl. Tabelle.
Was steht in Spalte \(x\), Zeile \(y\), was wird ausgegeben?
Ü: \(K_0\not\le_m (\mathbb{N}\setminus K_0)\), \((\mathbb{N}\setminus K_0)\not\le_m K_0\)
Def: \(Q\) heißt \(\operatorname{RE}\)-vollständig (bzgl. \(\le_m\)), falls:
\(Q\in\operatorname{RE}\) und \(\forall P\in\operatorname{RE}: P\le_m Q\).
Satz: \(K\) ist \(\operatorname{RE}\)-vollständig.
Beweis: Sei \(P\in\operatorname{RE}\), gegeben als \(\dom(\phi_i)\).
Dann \(x\in P\iff x\in\dom(\phi_i)\iff \phi_i(x)\downarrow \iff C(i,x)\in K\).
Die Reduktion (\(\le_m\)) benutzt also die Funktion \(x \mapsto C(i,x)\).
Übungen:
\(P\) ist RE-vollständig \(\Rightarrow\) \(P\notin\operatorname{REC}\).
\(P\) ist RE-vollst. \(\wedge P\le_m Q \wedge Q\in\operatorname{RE}\) \(\Rightarrow\) \(Q\) ist RE-vollst.
definiere den analogen Begriff REC-vollständig. Welche analogen Sätze gelten? Welche Mengen sind REC-vollst? (Zu viele, deswegen ist das nicht interessant)
Aufgaben für Übung KW49/KW50 sind markiert.
Aufgaben mit (!) enthalten evtl. schwere Teilaufgaben. Bilden Sie sich trotzdem eine Meinung.
(KW49) \(\le_m\) ist: transitiv, reflexiv?, symmetrisch? antisymmetrisch?
(KW 49) \(K\le_m K_0\).
Musterlösung: die Reduktionsfunktion \(f\) bildet Eingabe \(x\) ab auf einen Index der Funktion \(z \mapsto \phi_{P_1(x)} (P_2(x))\). Dann \(x\in K\iff \phi_{P_1(x)}(P_2(x))\downarrow \iff \phi_{f(x)}(f(x))\downarrow \iff f(x)\in K_0\).
(KW 49) (!) gehören diese Mengen zu \(\operatorname{REC}, \operatorname{RE}, \operatorname{coRE}\)?
\(\{ x\mid W_x =\emptyset\}, \{x\mid 1 = |W_x| \}, \{ x\mid W_x ~ \text{ist endlich} \}, \{ x\mid W_x ~ \text{ist unendlich} \}, \{x\mid W_x=\mathbb{N}\}, \{C(x,y) \mid W_x=W_y \},\)
dabei ist \(C\) eine Paar-Kodierung.
(KW 49) Definition: \(A\otimes B := \{C(x,y)\mid x\in A, y\in B\}\).
Für \(A,B\) in REC bzw. RE (d.h., 4 Fälle):
ist \(A\otimes B\) in REC bzw. RE? (d.h., je 2 Fragen)
Musterlösung (teilw.)
Es gilt \(\forall A\in \operatorname{REC}, B\in\operatorname{REC}: A\otimes B\in \operatorname{REC}\), denn \(c_{A\otimes B}(x)=c_A(P_1(x))\wedge c_B(P_2(x))\). Nach Voraussetzung sind \(c_A\) und \(c_B\) allgemein rekursiv, also auch \(c_{A\otimes B}\).
Es gilt nicht \(\forall A\in \operatorname{RE}, B\in\operatorname{RE}: A\otimes B\in \operatorname{REC}\). Gegenbeispiel: \(A=\mathbb{N}, B=K_0\). Dann gilt \(K_0\le_m \mathbb{N}\otimes K_0\) mit Reduktionsfunktion \(f_x\mapsto C(42,x)\). Aus \(K_0\notin\operatorname{REC}\) folgt \(\mathbb{N}\otimes K_0\notin\operatorname{REC}\).
Es gibt Mengen \(A\in\operatorname{RE}, B\in\operatorname{RE}\setminus\operatorname{REC}\) mit \(A\otimes B\in\operatorname{REC}\). Beispiel: \(A=\emptyset, B=K_0\), denn \(\emptyset\otimes K_0=\emptyset\in\operatorname{REC}\)
gibt es für jede \(A,B\in\operatorname{RE}\) mit \(A\cap B=\emptyset\)
\(f\in\operatorname{\text{Part}}\) mit \(f(A)=\{0\}\) und \(f(B)=\{1\}\) ?
\(f\in\operatorname{\text{Allg}}\) mit \(f(A)=\{0\}\) und \(f(B)=\{1\}\) ?
\(f:\mathbb{N}\to\mathbb{N}\) heißt Permutation, wenn \(f\) bijektiv ist.
Zeige, daß die (allgemein) rekursiven Permutationen bzgl. Nacheinanderausführung eine Gruppe bilden
(…aber die primitiv rekursiven nicht)
(KW 49) Jede unendliche rek. aufzählbare Menge hat eine unendliche entscheidbare Teilmenge.
aber (!) es gibt eine unendliche Menge ohne unendliche rek. aufzählbare Teilmenge.
(KW 50)
\(\{ x\mid W_x ~ \text{ist unendlich} \} \equiv_m \{ x\mid W_x = \mathbb{N}\}\)
Musterlösung: bezeichne die linke Seite mit \(A\), rechte mit \(B\).
Zu zeigen: \(A \le_m B\). Die Reduktionsfunktion \(f\) bildet \(x\) ab auf einen Index des folgenden Programms:
\(e \mapsto\) bei der Diagonal-Durchquerung der Tabelle von \((a,b) \mapsto \phi_x(a)\) hält nach genau \(b\) Schritten wird wenigstens \(e\) mal True angetroffen.
Dann \(x\in A \iff\) Tabelle enthält unendlich viele True \(\iff\) \(\phi_{f(x)}\) ist total \(\iff f(x)\in B\).
zu zeigen: \(B \le_m A\). Die Reduktionsfunktion \(f\) bildet \(x\) ab auf einen Index des folgenden Programms:
\(e \mapsto\) for i from 0 to e-1 do
\(\phi_x(i)\).
Dann \(x\in B \Rightarrow \phi_x\) total \(\Rightarrow \phi_{f(x)}\) total
und \(x\notin B \Rightarrow\) es gibt ein kleinstes \(i\) mit \(\phi_x(i)\uparrow\) \(\Rightarrow \dom(\phi_{f(x)})=\{0,\ldots,i\}\) und damit endlich, also \(f(x)\notin A\).
\((\mathbb{N}\setminus K_0) \le_m \{ x\mid W_x ~ \text{ist endlich} \}\)
\(\{ x\mid W_x ~ \text{ist endlich} \} \not\le_m K_0\)
\(\{ x\mid W_x \neq \emptyset \}\) ist RE-vollständig
(KW 50) Zeige \(M\le_m (\mathbb{N}\setminus M) \wedge M\in\operatorname{RE}\Rightarrow M\in\operatorname{REC}\).
Konstruiere \(M\) mit \(M\le_m (\mathbb{N}\setminus M)\) und \(M\notin\operatorname{REC}\)
bisher: Rechnen mit Zahlen,
jetzt: Rechnen mit Wörtern (Zeichenfolgen)
stellt Verbindung her zw. Berechenbarkeit und Theorie der formalen Sprachen
liefert ein genaueres Modell zur Messung des Ressourcenverbrauchs (in Komplexitätstheorie), (Rechnen mit beliebig großen Zahlen ist zu ungenau)
es war nie beabsichtigt, Turing-Maschinen tatsächlich zu bauen (anders als bei goto-Programmen)
aber die Natur macht es: (Umformungen von RNA)
Grundsatz: ein Schritt einer Rechnung ist eine lokal beschränkte Speicher-Änderung.
Speicher ist Zustand sowie Folge von Bändern
Band ist Folge von Zellen
jedes Band hat eine markierte Position (Kopfposition)
ein Schritt besteht aus: Lesen, Schreiben, Bewegen
(evtl. über den Rand, dabei wird das Band verlängert)
Zustandsmenge ist fixiert und endlich
Zeichenvorrat (Zelleninhalt) ist fixiert und endlich
Anzahl der Bänder ist fixiert und endlich
jedes Band ist endlich, aber nicht beschränkt
Bezeichnungen für \(k\)-Band-Turing-Maschine:
endliche Zustandsmenge \(Q\) , \(\bullet\) endliches Alphabet \(\Sigma\)
Leerzeichen \(\Box\notin\Sigma\), Bezeichnung \(\Sigma_\Box=\Sigma\cup\{\Box\}\)
Band-Inhalte: \(B(\Sigma):=\{ f:\mathbb{Z}\to \Sigma_\Box\) mit \(f^-(\Sigma)\) endlich \(\}\)
endliche Zahl \(k\ge 2\) (Anzahl der Bänder)
Die Konfigurationsmenge einer TM ist \(Q\times (B(\Sigma)\times \mathbb{Z})^k\).
Das Programm einer TM besteht aus
Initialzustand \(q_i\in Q\), Finalzustand \(q_f\in Q\)
Übergangstabelle \(t : Q \times \Sigma_\Box^k \hookrightarrow Q \times (\Sigma \times \{L,H,R\})^k\)
Definiert Relation (partielle Funktion) \(\to_M\) auf Konfigurationen durch …
mit 1 Arbeitsband.
\(\Sigma=\{0,1\}\), Leerzeichen \(\Box\)
\(Q=\{i,a,f\}\), initial: \(i\), final: \(f\)
für \(x\in\Sigma\): \(t(i,[x,p,y]) = (i,[(x,R),(x,R),(y,H)])\)
\(t(i,[\Box,p,y])=(a,[(\Box,H),(p,L),(y,H)])\)
für \(p\in\Sigma\): \(t(a,[x,p,y])=(a,[(x,H),(p,L),(p,R)])\)
\(t(a,[x,\Box,y])=(f,[(x,H),(\Box,H),(y,H)])\)
berechnet Wortfunktion \(\Sigma^*\to\Sigma^* : w\mapsto \text{reverse}(w)\)
für TM mit Einschränkung: jede Bewegung für Kopf 1 (Eingabe) und Kopf \(k\) (Ausgabe) ist \(\in\{H,R\}\)
Eingabe ist read-only, Ausgabe ist write-only
restliche Bänder heißen Arbeitsbänder
initiale Konfiguration für Eingabe \(u\in\Sigma^*\):
Zustand \(q_i\), Band 1 enthält \(u\) (ab 0), sonst leer, Köpfe: 0
finale Konfiguration mit Ausgabe \(v\in\Sigma^*\):
Zustand \(q_f\), Inhalt von Band \(k\) ist \(\dots,\Box,v,\Box,\dots\)
TM \(M\) berechnet \(f_M: \Sigma^*\hookrightarrow\Sigma^*\) mit
\(y=f_M(x)\), gdw. \(\exists c: \text{initial}(x)\to_M^* c\wedge \text{final}(c) \wedge \text{output}(c)=y\)
TM \(M\) mit Alphabet \(\{1,\#,\ldots\}\) (Zählzeichen, Trennzeichen)
berechnet Zahlfunktion \(g:\mathbb{N}^n\hookrightarrow\mathbb{N}\) mit
\(g(x_1,\ldots,x_n)=y\), gdw. \(f_M(1^{x_1}\#1^{x_2}\#\ldots\# 1^{x_n})=1^y\)
Wir nennen die so berechenbaren partiellen Funktionen Turing-berechenbar.
Genauer: \(\textsf{Turing}_k:=\) die durch TM mit \(k\) Arbeitsbändern berechenbaren partiellen Funktionen, \(\textsf{Turing}:=\bigcup_{k\ge 0}\textsf{Turing}_k\)
Ü: Nachfolger \(\in\textsf{Turing}\), Addition \(\in\textsf{Turing}\), Multipl. \(\in\textsf{Turing}\)
Nach der These von Church und Turing ist zu erwarten: \(\operatorname{\textsf{Goto}}=\operatorname{\textsf{While}}=\operatorname{\text{Part}}=\textsf{Turing}\),
Beweis durch Compiler von und nach Goto.
Satz: \(f\) ist TM-berechenbar \(\Rightarrow\) \(f\) ist Goto-berechenbar.
Beweis (Idee): simuliere Band mit Kopf durch \((l,r)\in\mathbb{N}^2\), d.h. zwei Register.
Jede Zahl ist Wort zur Basis \(b = 1+|\Sigma|\).
In \(l\) der Bandinhalt links vom Kopf,
in \(r\) der Bandinhalt rechts vom Kopf (gespiegelt).
Zeichen am Kopf lesen: \(r\) modulo \(b\).
Zeichen \(x\) schreiben und Kopf nach rechts: \(l' := b\cdot l+x; r'=\lfloor r/b\rfloor;\)
für diese Rechnungen braucht man noch ein Register, insgesamt: \(k\) Bänder \(\Rightarrow\) \(2k+1\) Register
Satz: \(f\) ist Goto-berechenbar \(\Rightarrow\) \(f\) ist Turing-berechenbar.
Beweis (Idee):
\(k\) Register \(\to\) \(k\) Arbeits-Bänder
Register \(i\) hat Inhalt \(x\) \(\to\) Arbeits-Band \(i\) hat Inhalt \(1^x\)
Programmablaufsteuerung: Befehlsnummer (PC) im Zustand der TM merken
Ü: ergänze Details zur Herstellung der Initialkonfiguration, Ablesen des Resultates aus Finalkonfiguration
Mehrere Arbeitsbänder sind nützlich, aber nicht nötig:
Satz: \(\forall k\ge 1: \textsf{Turing}_k =\textsf{Turing}_1\).
Beweis (Idee):
Kodiere Inhalte der \(k\) Zellen auf Position \(p\) der Arbeitsbänder in ein einziges Zeichen aus \(\Sigma^k_\Box\).
Beachte bei Realisierung:
es müssen dann immer alle Köpfe genau untereinander stehen
es werden nicht die Köpfe, sondern die Bänder bewegt,
eine simulierte Bewegung eines Kopfes ändert das gesamte simulierte Band
nach voriger Idee kann man Eingabe-, Ausgabe- und Arbeitsbänder in ein einziges Band kodieren
diesen Bandinhalt in zwei Registern \(x,y\) verwalten
zur Simulation eines Schrittes (Division, Multiplikation mit \(|\Sigma|+1\)) benötigt man ein drittes Register \(z\)
diese drei Register \(x,y,z\) kann man durch zwei simulieren: in \(a\) steht immer \(2^x 3^y 5^z\), und \(b\) zum Rechnen.
\(\Rightarrow\) das Halteproblem ist bereits für While- (oder Goto-)-Programme mit 2 Registern (die nur Inc/Dec ausführen) unentscheidbar.
…für 1 Register entscheidbar (spezieller Kellerautomat)
Ein einseitig unendliches Band ist ein Band, dessen Kopf nur Positionen \(\ge 0\) einimmt.
(bei unserer Def. der TM gilt: Ein- und Ausgabeband sind einseitig unendlich, Arbeitsbänder nicht.)
Begründen Sie, daß man ein unbeschränktes (d.h. zweiseitig unendliches) Band durch zwei einseitig unendliche Bänder schrittweise simulieren kann.
(schrittweise: ein Schritt der Original-Maschine \(\Rightarrow\) ein Schritt in der simulierenden Maschine)
Wir nennen einen TM-Befehl stationär, wenn dabei alle Köpfe stehenbleiben.
Beweisen Sie, daß jede TM-berechenbare Wortfunktion auch durch ein TM-Programm ohne stationäre Befehle berechnet werden kann.
Darstellungen von Gruppen
durch Generatoren und Relationen
Bsp: \(G=\langle a,b\mid a^2=b^2=(ab)^2=1 \rangle\)
Symmetriegruppe des Rechtecks (Kleinsche 4-Gruppe)
(\(a,b\) sind Spiegelungen, was ist \(ab\)?)
Rechnen in \(G\) : \(bab^3a^3ba =_G\dots =_G a^2ba\)
Wortproblem: gegeben \(G=\langle \dots\mid R\rangle, u, v\), gilt \(u=_G v\)?
Felix Klein (1849–1925, in Leipzig: 1880–1886)
Erlanger Programm (der Geometrie), vgl. auch \(\equiv_m, \le_m\)
(Syntax) Regelsystem \(R\subseteq \Sigma^*\times\Sigma^*\)
(Semantik) Teilwort-Ersetzungs-Relation \(\to_R\) auf \(\Sigma^*\) \(u\to_R v :\iff \exists p\in\Sigma^*:\exists (l,r)\in R:\exists q\in\Sigma^*: u=plq\wedge prq=v\)
Bsp. \(\Sigma=\{1,A\}, R=\{(A1,11A),(AE,\epsilon)\}\). Nf. von \(k111\)?
Markov-Algorithmus \(:=\) SRS \(R\) mit Strategie \(s\)
zur Auswahl genau eines Nachfolgers (z.B. leftmost)
Andrej Markov Jr., 1903 – 1979
die durch MA \((R,s)\) berechnete Wortfunktion:
\(f_R(u)=v \iff \textsf{initial}(u)\to_{R,s}^* v\wedge \textsf{final}(v)\),
wobei \(\textsf{initial}(w):= AwE\), \(\textsf{final}(w):=w\) ist \(R\)-Normalform
die durch Markov-Algorithmus berechnete Zahlfunktion:
kodiere Eingabe \(x\in\mathbb{N}^k\) als \(1^{x_1}\#\ldots\#1^{x_k}\)
Satz: für jede Wortfunktion \(f:\Sigma^*\hookrightarrow\Sigma^*\) gilt:
\(f\) ist Markov-berechenbar \(\iff\) \(f\) ist Turing-berechenbar
Beweis-Plan \(\Rightarrow\)
\(w\) auf Arbeitsband
TM bestimmt Regel und Stelle der Anwendung
Beweis-Plan \(\Leftarrow\)
kodiere alle Bänder in eines
übersetze Konfig \((q,b,k)\) in Wort \(b[\dots, k-1] ~q~ b[k,\dots]\)
übersetze TM-Befehl \((q,x)\to(q',x',R)\)
in SRS-Regel \(qx \to x'q'\), entspr. für \(H,L\) (Übung)
für dieses \(R\) ist \(\to_R\) partielle Fkt. \(\Sigma^* Q \Sigma^*\hookrightarrow\Sigma^* Q \Sigma^*\)
\(E_{\textsf{Markov}} := \{ (R,u,v) \mid u \to_{R,\det}^* v \}\), \(E_{\textsf{SRS}} := \{ (R,u,v) \mid u \to_R^* v \}\)
Eigenschaften:
\(E_{\textsf{SRS}}\in\operatorname{RE}\) (Beweis: Übung)
\(E_{\textsf{SRS}}\notin\operatorname{REC}\)
Beweis: zeige \(K_{\textsf{Turing}}\le_m E_{\textsf{Turing}}\le_m E_{\textsf{Markov}}\le_m E_{\textsf{SRS}}\)
TM \(M\) hält (nach Def.) durch Erreichen des Zustandes \(q_f\).
Konstruiere \(M'\): wie \(M\), aber für \(q_f\) Regeln zum Löschen aller Bänder, dann Halt in neuem, finalen Zustand \(q_f'\)
Dann \(M(u)\downarrow \iff M'(u)=v_0=\) leeres Band (Bänder)
D.h. Reduktion (für \(\le_m\)) durch \((M,u)\mapsto (M',u,v_0)\)
ein leicht zu definierendes kombinatorisches Problem
(eine Eigenschaft einer Folge von Paaren von Wörtern)
(leicht heißt: Def. PCP ist kürzer als Def. TM)
das trotzdem schwierig ist.
(schwierig heißt: \(\operatorname{\textsf{PCP}}\notin\operatorname{REC}\))
ist Hilfsmittel für Beweise der Unentscheidbarkeit von Eigenschaften formale Sprachen, logischer Formeln, usw.
(Hilfsmittel heißt: wir verwenden \(\le_m\))
Emil Post (1897 – 1954)
Eine Instanz des Postschen Korrespondenzproblems besteht aus:
endl. Menge \(\Sigma\) (Bsp. \(\{0,1\}\)), endl. Menge \(\Gamma\) (Bsp, \(\{a,b,c\}\)),
zwei Morphismen (Wdhlg. Def.?) \(f,g:\Gamma^*\to\Sigma^*\)
Bsp. \(f(a)=10, f(b)=101, f(c)=1,\)
\(g(a)=1, g(b)=010101, g(c)=0\)
\(w\in\Gamma^+\) heißt Lösung der Instanz, wenn \(f(w)=g(w)\)
\(\operatorname{\textsf{PCP}}\) ist die Menge der lösbaren PCP-Instanzen
Für das Beispiel gilt: \(\epsilon\) ist keine Lösung. \(ab\) ist keine Lösung. Keine Lösung beginnt mit \(ab\). Es gibt eine Lösung. Es gibt unendliche viele Lösungen.
Ziel: berechenbare Funktion \(f\) mit für alle \(R\), Wörter \(u,v\):
\(u\to_R^* v \iff f(R,u,v)\in\operatorname{\textsf{PCP}}\)
Sei \(f(R,u,v) = I = (\Gamma,\Sigma, g,h)\)
Plan: \(w\) ist Lösung von \(I\) gdw.
Lösungswort \(g(w)=h(w) = Au_0\#u_1\#\ldots\#u_n\#E\)
mit \(u=u_0\) und \(\forall i: u_i\to_R u_{i+1}\) und \(u_n=v\)
\(I = \begin{array}{c||c|c|c|c|c|c|c|c} g & A & l_1 & \dots & l_{|R|} & v \# E & x_1 & \dots & x_k\\ \hline h & A u \# & r_1 & \dots & r_{|R|} & E & x_1 & \dots & x_k \end{array}\)
mit \(\Sigma=\{x_1,\ldots,x_k\}\)
außer dem gewünschten Lösungswort
gibt es triviale Lösungen wegen der Kopier-Regeln.
PCP \(\Rightarrow\) MPCP, Lösungen sollen mit ersten Paar beginnen
(in der Literatur oft: modifiziertes PCP, MPCP)
zusätzlicher Parameter \(a\in\Gamma\)
\(\textsf{MPCP}= \{(\Gamma,\Sigma,f,g,a)\mid \exists w: f(aw)=g(aw) \}\)
Satz: \(\textsf{MPCP}\le_m\operatorname{\textsf{PCP}}\)
Beweis: \(I:(\Gamma,\Sigma,f,g,a)\mapsto I':(\Gamma \cup\{e\},\Sigma\cup\{M,E\},f',g')\)
neuer Buchstabe \(M\) soll an jeder zweiten Stelle von \(f'(w')=g'(w')\) vorkommen,
benutze Morphismen \(L(x)=Mx, R(x)=xM\)
\(\begin{array}{c||c|c|c|c|c|c|c} f' & L(f(a))M & R(f(b)) & \dots & E \\ \hline g' & L(g(a)) & L(g(b)) & \dots & ME \end{array}\)
\(aw\) löst \(I\) gdw. \(awe\) löst \(I'\),
jede Lösung von \(I'\) beginnt mit \(a\) und endet mit \(e\)
wir haben nun gezeigt: \(E_{\textsf{SRS}} \le_m \textsf{MPCP}\le_m \operatorname{\textsf{PCP}}\)
aus \(E_{\textsf{SRS}}\notin\operatorname{REC}\) folgt \(\operatorname{\textsf{PCP}}\notin\operatorname{REC}\)
damit beweisen wir nun die Unentscheidbarkeit weiterer Probleme aus den Bereichen
formale Grammatiken
Logik
Def. \(\textsf{CFGine}= \{ (G_1,G_2)\mid G_i\in\textsf{CFG}, L(G_1)\cap L(G_2)\neq\emptyset \}\)
(context-free grammar intersection non-emptiness)
Satz: \(\textsf{CFGine}\notin\operatorname{REC}\). Beweis: \(\operatorname{\textsf{PCP}}\le_m \textsf{CFGine}\)
Beweis: gegeben PCP-Instanz \(I=(\Gamma,\Sigma,f,g)\), konstruiere
\(G_1\) mit \(L(G_1)=\{ \textsf{reverse}(g(w))\# f(w) \mid w\in\Gamma^+ \}\)
\(G_2\) mit \(L(G_2)=\{\textsf{reverse}(u)\#u\mid u\in\Sigma^*\}\)
Übung: untersuche Mitgliedschaft in REC, RE, coRE für
\(\{ (G_1,G_2)\mid G_i\in\textsf{CFG}, L(G_1)\subseteq L(G_2) \}\)
\(\{ (G_1,G_2)\mid G_i\in\textsf{CFG}, L(G_1) = L(G_2) \}\)
\(\{ G \mid G\in\textsf{CFG}, L(G)=\Sigma^* \}\), \(\{ G \mid G\in\textsf{CFG}, L(G)=\emptyset \}\)
\(\{ G \mid G\in\textsf{CFG},\) \(G\) ist eindeutig \(\}\)
Das Allgemeingültigkeitsproblem \(\textsf{APL}\) ist
Eingabe: PL-Formel \(F\), ohne freie Variablen, in Sign. \(\Sigma\),
Frage: \(F\) allgemeingültig? (gilt in jeder \(\Sigma\)-Struktur \(S\))
Bsp: \((\exists x:\forall y: P(x,y))\to(\forall y:\exists x:P(x,y))\)
Satz: \(\operatorname{\textsf{PCP}}\le_m\textsf{APL}\). Folg. \(\textsf{APL}\notin\operatorname{REC}\)
Beweis-Plan: Aus PCP-Instanz mit Paaren \((ab,ba),\dots\) konstruiere Formel \((F_1\wedge F_2)\to \exists R(x,x)\) mit
\(F_1 = R(a(b(e)),b(a(e))) \wedge \dots\)
\(F_2 = \forall x,y: R(x,y)\rightarrow R(a(b(x)),b(a(x)))\wedge\dots\)
Die Theorie einer Struktur \(S\) ist die Menge der Formeln \(F\) mit \(S\models F\).
Die Theorie der Arithmetik \(\textsf{TA}\) besteht aus allen wahren Aussagen über \(\mathbb{N}\) in der Signatur \(\{0/0,1/0,+/2,\cdot/2\}\)
Bsp. \((\exists x:\forall y: x \neq 2\cdot y)\in\textsf{TA}\)
Satz (1931, Kurt Gödel, 1906–1978): \(\textsf{TA}\notin\operatorname{REC}\).
Beweis: \(E_{\operatorname{\textsf{While}}}\le_m\textsf{TA}\), denn
die Zustandsübergangsrelation \(\to_P\) eines While-Programms kann arithmetisiert werden.
Für \(P=\text{while}(x)Q\) verwende
\(\exists t,c:\) \(c\) ist Kodierung einer Folge von \(t\) Zuständen …
Bezeichnung: eine PL-Formel \(F\) heißt
wahr, wenn \(\forall S: S\models F\) (gilt in jeder Struktur)
ableitbar (durch Inferenzsystem (Axiomen und Regeln))
Satz: Menge der ableitbaren Formeln \(\in\) RE
Beweis: Inf.-Syst. ist endlich und jede Ableitung ist endlich.
Bezeichnung: ein Inferenzsystem heißt
korrekt, wenn jede ableitbare Formel wahr ist
vollständig, wenn jede wahre Formel ableitbar ist
Satz (Gödel): jedes korrekte Inferenzsystem für die Arithmetik ist unvollständig.
Bew.: \(\text{co-}\textsf{TA}\le_m \textsf{TA}\) (wg. \(F\mapsto \neg F\)), \(\textsf{TA}\in\operatorname{RE}\cap\operatorname{coRE}=\operatorname{REC}\)
In der Kleinschen 4-Gruppe gilt: \(ab=ba\). Beweise durch
geometrischen Anschauung,
eine Gleichungskette unter Benutzung der Relationen
Für das SRS \(\{ab\to baa\}\): Normalform von \(a^kb\), von \(a b^k\).
Ergänze Simulation der TM durch MA (Kopfbewegungen \(H\), \(L\))
autotool-Aufgabe PCP
Für PCP mit \(|\Sigma|=1\):
Geben Sie je eine lösbare und eine nicht lösbare Instanz mit \(|\Gamma|=3\) an.
Geben Sie ein Entscheidungsverfahren an.
Die folgende Variante des PCP ist entscheidbar:
Eingabe: Morphismen \(f,g:\Gamma^*\to\Sigma^*\),
Lösung: Wörter \(w_1,w_2\in\Gamma^+\) mit \(f(w_1)=g(w_2)\)
(Hinweis: endliche Automaten)
Aufgaben auf Folie eine unentsch. Eig. von CFG
Hinweis: \(\Sigma^*\setminus L(G_2)\) ist auch kontextfrei.
(1. warum? 2. was nützt es?)
bisher: deterministische Rechnungen
Rechnung ist Pfad
ist erfolgreich, falls finaler Zustand erreicht wird
jetzt: Such-Aufgaben (nichtdeterministische Rechnungen)
Rechnung ist Baum (d.h., mglw. mehrfach verzweigt)
ist erfolgreich, falls ein finales Blatt existiert
alternative Sichtweise: Orakel-Berechnung
ein Orakel beschreibt den Weg zum finalen Blatt,
deterministische Maschine verifiziert diesen Weg
\(M\in \operatorname{RE}\iff \exists i:M=\dom \phi_i\)
\(x\in M\iff\exists y:\) Rechn. \(\phi_i(x)\) hält nach genau \(y\) Schritten
\(\{C(x,y)\mid\) Rechn. \(\phi_i(x)\) hält nach genau \(y\) Schr. \(\} \in \operatorname{REC}\)
Satz: \(\forall M\subseteq\mathbb{N}: M\in \operatorname{RE}\iff\exists M'\in\operatorname{REC}: \forall x: x\in M\iff \exists y: C(x,y)\in M'\)
Ü: Beweis für \(\Longleftarrow\)
Bezeichnungen: \(y\) ist Orakel-Wort oder Zertifikat für \(x\).
Ü: falls \(\exists M'\in \operatorname{REC}:\forall x: x\in M \iff \exists y:C(x,y)\in M' \wedge y\le x\), dann \(M\in\operatorname{REC}\)
Def: eine Orakel-Maschine \(A\) hat Eingabeband (Alphabet \(\Sigma\)), Orakelband (Alphabet \(\Gamma\)) und Arbeitsbänder
Def: die von \(A\) akzeptierte Sprache \(\textsf{Lang}_{\textsf{Acc}}(A)\subseteq\Sigma^*\):
Menge aller Eingabewörter \(x\), für die ein Orakelwort \(y\) existiert, so daß Rechnung \(M(x,y)\) erfolgreich hält.
nach dieser Def: das Orakel sieht \(x\) und schreibt \(y\), dann rechnet (verifiziert) \(A\) (deterministisch)
alternative Sichtweise: \(y\) ist unbekannt, bei jedem Lesen eines unbekannten Zeichens von \(y\) verzweigt die Rechnung: \(A\) ist nicht-deterministische TM
die Rechnung \(A(x)\) ist ein Baum \(T\), Eingabe wird akzeptiert, wenn \(T\) ein erfolgreiches Blatt enthält
bis jetzt: Berechenbarkeit als qualitativer Begriff
(eine Funktion ist berechenbar oder nicht,
eine Menge ist entscheidbar oder nicht)
ab jetzt: quantitative Untersuchung:
für berechenbare Funktionen/entscheidbare Mengen:
mit welchem Aufwand läßt sich Rechnung durchführen?
Komplexität sowohl für det. als auch für nichtdet. Berechnungsmodelle (Suchprobleme)
verwendet Methoden der Berechenbarkeitstheorie (insb. Reduktion, Vollständigkeit)
Ressourcen:
z.B. Rechenzeit, Speicherplatz, Kommunikationsaufwand
Komplexität eines Algorithmus (eines Programmes, einer Maschine):
Ressourcenverbrauch als Funktion der Eingabegröße
Bsp: die Komplexität von Bubblesort ist quadratisch.
Komplexität eines Problems: Komplexität für besten Algorithmus, der das Problem löst.
Bsp: die Komplexität des Sortierens ist \(\in \Theta(n\mapsto n\cdot\log n)\)
Komplexitätstheorie ist die Lehre von der Schwierigkeit von Problemen.
Zahlen sind hier: ganz, nichtnegativ und binärkodiert
zusammengesetzte Zahlen
\(\textsf{COMP}=\{ x \mid \exists y,z\ge 2: x=y\cdot z\}\)
Primzahlen
\(\textsf{PRIMES}=\{ x \mid x\ge 2\} \setminus \textsf{COMP}\)
Quadratzahlen
\(\textsf{SQUARES}= \{ x\mid\exists y: x=y^2\}\)
Motivation: u.a. Kryptographie
RSA-Schlüssel \(\in\textsf{COMP}\), aber die Ursache (die Faktoren) soll geheim bleiben
\(\textsf{AL}=\) die Menge der aussagenlogischen Formeln
\(b\models F\): die Belegung \(b\) erfüllt die Formel \(F\)
\(\textsf{SAT}=\{ F \mid F \in\textsf{AL}, \exists b: b\models F \}\)
Bsp. \(((x \to \neg y)\wedge (x\leftrightarrow y))\in\textsf{SAT}\), \((x \wedge \neg x)\notin\textsf{SAT}\)
Spezialfälle (durch syntaktische Einschränkungen)
CNF-SAT:
wie oben und \(F\) ist in konjunktiver Normalform
\(k\)-CNF-SAT:
…mit \(\le k\) Literalen je Klausel
Motivation: Entwurf und Überprüfung von digitalen Schaltungen
Schaltkreis ist DAG mit:
Startknoten (keine Vorgänger): Eingaben
andere Knoten: markiert mit Boolescher Op. (\(\wedge,\vee,\neg\))
Endknoten (keine Nachfolger): Ausgaben
jeder Knoten realisiert Bool. Fkt. der Eingabe
Schaltkreis-Erfüllbarkeit \(\textsf{CIRC}\textsf{SAT}=\{C\mid\) \(C\) ist unärer Schaltkreis (mit einer Ausgabe) \(\wedge\exists\) Eingabe \(e\) mit Ausgabe \(C(e)=1\), Schreibweise \(e\models C\) \(\}\)
Satz: \(\textsf{CIRC}\textsf{SAT}\in\textsf{NP}\),
Beweis: das Orakel rät die Eingabe \(e\), dann kann \(C(e)\) in Polynomialzeit berechnet werden (z.B. schichtweise)
eine \(k\)-Färbung eines Graphen \(G=(V,E)\) ist eine Abbildung \(f:V\to\{1,2,\ldots,k\}\)
die Färbung \(f\) von \(G=(V,E)\) ist konfliktfrei,
wenn \(\forall xy\in E: f(x)\neq f(y)\)
\(k\textsf{COL}:= \{ G \mid \exists f:\) \(f\) ist konfliktfreie \(k\)-Färbung von \(G\) \(\}\)
Bsp: \(K_3\notin 2\textsf{COL}\), \(C_5\notin 2\textsf{COL}\),
Ü: finde \(G\) mit: \(G\) enthält keinen \(K_3\) und \(G\notin 3\textsf{COL}\)
Ü: jeder Knoten von \(G\) hat \(< k\) Nachbarn \(\Rightarrow\) \(G\in k\textsf{COL}\).
Motivation: Ressourcenzuordnungsprobleme,
z.B. Frequenzbereiche zu Funkzellen
bisher:
wg. These von Church und Turing war das Berechnungsmodell beliebig
wg. Gödelisierung war die Art der Eingabe (Zahlen, Wörter usw.) beliebig
jetzt:
wg. exakter Ressourcenmessung muß ein Modell fixiert werden (Turingmaschine)
wg. Komplexität als Fkt. der Eingabegröße
muß Größe exakt definiert werden
(Länge des Wortes auf dem Eingabeband, Länge der Binärkodierung einer Zahl)
für \(f:\mathbb{N}\to\mathbb{N}\) bezeichnet \(\textsf{DTIME}_{\textsf{Alg}}(f)\)
die Menge der TM \(M\) mit \(\forall x\in\textsf{Lang}_{\textsf{Acc}}(M)\)
\(\iff\) \(M\) akzeptiert \(x\) nach \(\le f(|x|)\) Schritten.
für \(f:\mathbb{N}\to\mathbb{N}\) bezeichnet \(\textsf{DTIME}_{\textsf{Prob}}(f)\)
die Menge der Sprachen \(L\) mit \(\exists M\in \textsf{DTIME}_{\textsf{Alg}}(f) : L=\textsf{Lang}_{\textsf{Acc}}(M)\).
Abkürzung \(\textsf{DTIME}= \textsf{DTIME}_{\textsf{Prob}}\)
Satz: \(f\) berechenbar \(\Rightarrow\) \(\textsf{DTIME}(f)\subseteq \operatorname{REC}\)
für Menge \(F\) von Funktionen: \(\displaystyle\textsf{DTIME}(F) = \bigcup_{f\in F} \textsf{DTIME}(f)\)
Abkürzung: \(\textsf{P}= \text{PTIME}=\textsf{DTIME}(\text{Menge der Polynome})\)
\(\{ w \mid w\in\{0,1\}^*, w=\overline{w}\}\in\textsf{P}\), \(\textsf{CFL}\subseteq \textsf{P}\), \(2\textsf{COL}\in\textsf{P}\), \(2\textsf{SAT}\in\textsf{P}\)
für \(f:\mathbb{N}\to\mathbb{N}\) bezeichnet \(\textsf{NTIME}_{\textsf{Alg}}(f)\) die Menge der Orakel-TM \(M\) mit \(\forall x: x\in\textsf{Lang}_{\textsf{Acc}}(M)\) \(\iff\) es gibt ein Orakelwort \(y\) mit: \(M(x,y)\) akzeptiert in \(\le f(|x|)\) Schritten.
(dabei werden \(\le f(|x|)\) Zeichen von \(y\) gelesen)
entsprechend \(\textsf{NTIME}_{\textsf{Prob}}(f), \textsf{NTIME}(f), \textsf{NTIME}(F)\)
Ü: \(f\) berechenbar \(\Rightarrow\) \(\textsf{NTIME}(f)\subseteq \operatorname{REC}\)
Abkürzung \(\textsf{NP}=\textsf{NPTIME}=\textsf{NTIME}(\text{Polynome})\)
Bsp. \(\textsf{COMP}\in\textsf{NP}, \textsf{SAT}\in\textsf{NP}, \forall k:k\textsf{COL}\in\textsf{NP}\)
Satz: \(A\in\textsf{NP}\wedge B\in\textsf{NP}\Rightarrow (A\cup B)\in\textsf{NP}\)
Satz: \(\textsf{P}\subseteq \textsf{NP}\) (trivial) , Frage \(\textsf{P}=\textsf{NP}\) (schwierig: \(10^6\) $, http://www.claymath.org/millennium-problems/p-vs-np-problem)
Def: \(\textsf{coNP}= \{ L \mid (\Sigma^*\setminus L)\in\textsf{NP}\}\)
Bsp: \(\textsf{PRIMES}\in\textsf{coNP}\) wegen \(\textsf{COMP}\in\textsf{NP}\)
es gilt auch \(\textsf{PRIMES}\in\textsf{NP}\), Beweis benötigt etwas Zahlentheorie
\(\textsf{PRIMES}\in\textsf{P}\),
Manindra Agrawal, Neeraj Kayal, Nitin Saxena, 2004.
bis jetzt:
es gibt Analogien zwischen:
Berechenbarkeit: \(\operatorname{REC}, \operatorname{RE}, \operatorname{coRE}\)
Komplexität: \(\textsf{P},\textsf{NP},\textsf{coNP}\)
der Unterschied ist, daß man \(\operatorname{REC}\neq\operatorname{RE}\), \(\operatorname{RE}\neq\operatorname{coRE}\) und \(\operatorname{RE}\cap\operatorname{coRE}=\operatorname{REC}\) beweisen kann,
die entsprechenden Komplexitätsaussagen bisher nicht
nächste VL:
Reduktion (Vergleich der Komplexität von Problemen)
Vollständigkeit (zur Def. der schwersten Probleme einer Klasse)
Markierte Aufgaben besonders empfohlen zur Diskussion in Übung KW 54.
(KW54) Beweise: für alle \(M'\in \operatorname{REC}\) und totale berechenbare \(f:\mathbb{N}\to\mathbb{N}\) gilt \(\{ x \mid \exists y:C(x,y)\in M' \wedge y\le f(x)\} \in\operatorname{REC}\)
auf Deutsch: wenn die Größe der Orakelzahlen durch eine berechenbare Funktion beschränkt ist, dann ist jede mit diesem Orakel entscheidbare Menge auch ohne Orakel entscheidbar.
FP und LOOP:
Geben Sie eine Funktion \(f\in\operatorname{\textsf{LOOP}}\) an, die nicht in Polynomialzeit berechenbar ist (Hinweis: z.B., weil sie zu schnell wächst)
\(\operatorname{\textsf{LOOP}}^-\)-Programme: wie LOOP, aber
zusätzlich ein Befehl \(\textsf{Copy}(x,y)\) mit Semantik \(y:= x\)
Falls \(\operatorname{\textsf{Inc}}(x)\) in einer Schleife vorkommt, dann heißt \(x\) vergiftet. Falls \(\textsf{Copy}(x,y)\) und \(x\) vergiftet, dann auch \(y\) vergiftet. Vergiftetes Register darf nicht als Schleifenzähler benutzt werden.
Beweise: Addition, Multiplikation \(\in \operatorname{\textsf{LOOP}}^-\).
Beweise: \(\operatorname{\textsf{LOOP}}^-\)-Programme haben polynomielle Laufzeit
(KW 54) Abschlußeigenschaften
ist \(\textsf{P}\) abgeschlossen unter: Vereinigung, Durchschnitt, Komplement? (trivial)
… Verkettung? (ja.) Stern?
die gleichen Fragen für \(\textsf{NP}\).
Zahlen
\(\textsf{SQUARES}\in\textsf{NP}\) (trivial), \(\textsf{SQUARES}\in \textsf{P}\)
\(\textsf{PRIMES}\in\textsf{NP}\) (Satz von Fermat, primitive Wurzeln)
Graphen
3COL: autotool
gesucht: ein \(G\) mit \(G\notin 3\textsf{COL}\) und \(G\) enthält kein \(K_3\) (Dreieck)
(KW 54) für alle \(G\) mit \(\deg(G)< k\) gilt \(G\in k\textsf{COL}\).
Hinweis: geben Sie einen Algorithmus an, der unter dieser Voraussetzung eine \(k\)-Färbung für \(G\) konstruiert.
Für welche Graphen gilt: \(G\) hat Maximalgrad \(k\) und \(G\notin k\textsf{COL}\)?
Logik
CNF-SAT: autotool
(KW 54) \(2\textsf{CNF}\textsf{SAT}\in\textsf{P}\) (schreibe jede Klausel als Implikation und betrachte einen dazu passenden Graphen)
\(\textsf{DNF}\textsf{SAT}\in\textsf{P}\) (disjunktive Normalform)
nach bisherigen Definitionen/Beispielen:
\(\textsf{P}\): Klasse der (auf sequentiellen Maschinen) effizient lösbaren Probleme
\(\textsf{NP}\): enthält häufig vorkommende Suchprobleme
für (neues) Problem \(L\) wüßte man gern: \(L\in \textsf{P}\) oder \(L\notin\textsf{P}\)?
bis heute ist kein \(L\in\textsf{NP}\setminus\textsf{P}\) bekannt, obwohl es viele Kandidaten gibt.
Bekannt ist jedoch eine Charakterisierung der schwersten Probleme in NP:
die Klasse NPc der NP-vollständigen Probleme
Def: \(\textsf{FTIME}(f):=\) die in Zeit \(\le f(|x|)\) auf DTM berechenbaren Fkt., \(\textsf{FP}:= \textsf{FTIME}(\text{poly})\).
Def: \(A\le_{\textsf{P}}B := \exists f\in\textsf{FP}:\forall x\in\Sigma^*: x\in A\iff f(x)\in B\).
Bsp: \(\textsf{DHC}\le_{\textsf{P}}\textsf{HC}\).
\(\textsf{HC}:= \{ G\mid\) \(G\) ist ungerichteter Graph und \(G\) enthält Kreis durch alle Knoten \(\}\) (Hamiltonian Circuit)
\(\textsf{DHC}:= \{ G\mid\) \(G\) ist gerichteter Graph und \(G\) enthält gerichteten Kreis durch alle Knoten \(\}\) (Directed HC)
Beweis: \(f(V,E)=(V\times\{1,2,3\} ,E')\) mit \(E' = \{ (v,1)(v,2) \mid v\in V\}\cup\{ (v,2)(v,3) \mid v\in V\}\cup \{ (u,3)(v,1) \mid (u,v)\in E\).
zu zeigen sind für \(f\): Korrektheit, Laufzeit
vgl.: \(\le_m\) ist transitiv,
Beweis: sei \(A \le_{\textsf{P}}B\) mit Reduktionsfunktion \(f\),
\(B\le_{\textsf{P}}C\) mit Reduktionsfunktion \(g\).
zeige: \(A\le_{\textsf{P}}C\) durch Reduktionsfunktion \(h:x\mapsto g(f(x))\)
Korrektheit ist offensichtlich, Laufzeit: folgt aus:
Satz: \(f\in\textsf{FP}\wedge g\in\textsf{FP}\Rightarrow (x\mapsto g(f(x)))\in\textsf{FP}\).
Bew.: sei \(f\in\textsf{FTIME}(n\mapsto c\cdot n^k), g\in\textsf{FTIME}(n\mapsto d\cdot n^l)\).
die Ausgabe von \(f\) ist die Eingabe von \(g\)
Ausgabenlänge \(\le\) Rechenzeit
daraus folgt \((x\mapsto g(f(x))\in\textsf{FTIME}(n \mapsto \ldots \cdot n^{\dots})\)
Satz: \(A\le_{\textsf{P}}B \wedge B\in\textsf{P}\Rightarrow A\in\textsf{P}\)
Beweis: benutze Abschluß von \(\textsf{FP}\) bzg. Komposition für
die Reduktionsfunktion \(f\) von \(A\) nach \(B\)
die charakteristische Fkt. \(c_B\) von \(B\)
Satz: \(A\le_{\textsf{P}}B \wedge B\in\textsf{NP}\Rightarrow A\in\textsf{NP}\)
Beweis: sei \(f\) die Reduktionsfunktion von \(A\) nach \(B\),
\(c_B\) wird orakel-berechnet \(M:(x,y)\mapsto\{0,1\}\).
Dann wird \(c_A\) orakel-berechnet durch \((x,y)\mapsto M(f(x),y)\)
zu betrachten sind: Korrektheit, Laufzeit, Orakelgröße.
vgl. \(A\le_m B \wedge B\in\operatorname{REC}\Rightarrow A\in\operatorname{REC}\), \(A\le_m B \wedge B\in\operatorname{RE}\Rightarrow A\in\operatorname{RE}\).
Def:\(B\) heißt NP-schwer, gdw. \(\forall A\in\textsf{NP}: A\le_{\textsf{P}}B\).
Def: \(B\) NP-vollständig, gdw. \(B\) NP-schwer und \(B\in\textsf{NP}\)
\(\textsf{NPc}:= \{B\mid \text{\)B\(ist NP-vollständig}\}\)
Satz (Steven Cook, 1971): \(\textsf{SAT}\in\textsf{NPc}\)
wir zeigen zunächst: \(\textsf{CIRC}\textsf{SAT}\in\textsf{NPc}\)
Bew: \(\textsf{CIRC}\textsf{SAT}\in\textsf{NP}\) wurde schon gezeigt.
Bleibt zu zeigen: \(\textsf{CIRC}\textsf{SAT}\) ist NP-schwer. Dazu:
gegeben \(A\in \textsf{NP}\), zu zeigen ist \(A\le_{\textsf{P}}\textsf{CIRC}\textsf{SAT}\).
Bew: gegeben \(A\in \textsf{NP}\), zu zeigen ist \(A\le_{\textsf{P}}\textsf{CIRC}\textsf{SAT}\).
\(A=\textsf{Lang}_{\textsf{Acc}}(M)\) für O.-TM \(M\) mit Zeitschranke \(s\in\text{poly}\)
Reduktionsfunktion \(f: x\mapsto\) Schaltkreis \(C\), der Konfigurationsfolge einer erfolgreichen Rechnung von \(M\) mit \(\le s(|x|)\) Schritten bei Eingabe \(x\) und Orakelwort \(y\) beschreibt, d.h., \(x\in A\iff \exists y: C(x,y)=1\)
Eingangsknoten: Kodierung von \(x,y\)
andere Knoten: indiziert durch Platz \(p\) und Zeit \(t\), \(K(p,t)\) enthält Kodierung von Zeichen, Kopfposition, Zustand
Ausgabeknoten: akzeptierender Zustand wurde erreicht
\(C\) kann in FP konstruiert werden (Zeit und Platz sind \(\le s(|x|)\) )
Gregory Tseitin, 1966
Plan: aus Schaltkreis \(C\) wird Formel \(G\) konstruiert
mit Knoten von \(C\) \(=\) \(\textsf{Var}(G)\)
und \(\forall e: e \models C \iff \exists b:e\subseteq b \wedge b\models G\).
(jedes Modell von \(G\) ist Erweiterung eines Modells von \(C\) und jedes Modell von \(C\) läßt sich zu Modell von \(G\) erweitern)
Realisierung: für jeden nicht-Eingabeknoten \(k\) von \(C\) mit Vorgängern \(k_1,k_2,\dots\) und Verknüpfung \(f\):
Menge von CNF-Klauseln, die äquivalent ist zu \(k\leftrightarrow f(k_1,k_2,\dots)\).
Einzelheiten, Bsp \(f=\wedge\).
\(\overline k\vee k_1, \overline k\vee k_2,\dots, k\vee\overline{k_1}\vee \overline{k_2}\vee\dots\)
(andere Verknüpfungen: Übung)
Folgerung: \(\textsf{CIRC}\textsf{SAT}\le_{\textsf{P}}\textsf{CNF}\textsf{SAT}\le_{\textsf{P}}\textsf{SAT}\)
\(\textsf{CNF}\textsf{SAT}\) ist NP-schwer, \(\textsf{SAT}\) ist NP-schwer
Übung: \(\textsf{SAT}\le_{\textsf{P}}3\textsf{CNF}\textsf{SAT}\). Hinweis: \(\textsf{SAT}\le\textsf{CIRC}\textsf{SAT}\) und dann den Schaltkreis umformen, so daß bei unsere Reduktion \(\textsf{CIRC}\textsf{SAT}\le_{\textsf{P}}\textsf{CNF}\textsf{SAT}\) nur 3-Klauseln entstehen
wenn sich ein Anwendungsproblem \(L\) als NP-vollständig heraustellt, dann folgt:
es gibt derzeit keinen effizienten Algorithmus für \(L\)
\(L\le_{\textsf{P}}\textsf{SAT}\le_{\textsf{P}}\textsf{CNF}\textsf{SAT}\), d.h. man kann \(L\) lösen, wenn man CNFSAT lösen kann
…und gute CNFSAT-Solver gibt es tatsächlich
Niklas Een, Niklas Sörensson: http://minisat.se/
Wettbewerbe: http://satcompetition.org/
Einzelheiten: siehe VL Constraint-Programmierung http://www.informatik.uni-leipzig.de/~waldmann/
Es gilt: zu jeder Formel \(F\) gibt es eine äquivalente Formel \(G\) in disjunktiver Normalform. Es gilt auch: DNFSAT\(\in\textsf{P}\). Warum folgt daraus nicht \(\textsf{SAT}\in\textsf{P}\)?
Bem: \(\textsf{SAT}\in\textsf{P}\) ist damit nicht ausgeschlossen, es geht nur darum, daß es so jedenfalls nicht folgt.
(KW 55) Für den Schaltkreis für die Formel \((x_1\wedge x_2)\vee x_3\):
Führe die Tseitin-Transformation durch.
gib eine CNF an für genau eine von \((x_1,\ldots,x_n)\) ist wahr.
(z.B. \(n=4, n = 8\))
gib, falls möglich, eine kleinere erfüllbarkeitsäquivalente CNF dafür an (d.h.: mit Zusatzvariablen, und so, daß die Tseitin-Spezifikation wahr ist)
(KW 55) Def. \(A\equiv_{\textsf{P}} B\) gdw. \(A\le_{\textsf{P}}B\) und \(B\le_{\textsf{P}}A\).
Seien \(A,B\in\textsf{P}\). Wann gilt und gilt nicht \(A\equiv_{\textsf{P}} B\)?
(KW 55) zeige \(A\in \textsf{NPc}\wedge B\in\textsf{NPc}\Rightarrow A\equiv_{\textsf{P}} B\)
(KW 55) Für \(A,B\subseteq\Sigma^*\) gilt \(A\le_{\textsf{P}}B \iff (\Sigma^*\setminus A)\le_{\textsf{P}}(\Sigma^*\setminus B)\).
man könnte definieren: \(B\) ist P-vollständig bzgl \(\le_{\textsf{P}}\) gdw. \(B\in\textsf{P}\) und \(\forall A\in\textsf{P}: A\le_{\textsf{P}}B\).
Das ist aber nicht interessant, denn sehr viele Mengen aus P haben diese Eigenschaft — welche nicht?
(KW 55) Es gilt \(3\textsf{COL}\le_{\textsf{P}}\textsf{SAT}\) (warum? erfordert keine Rechnung, sondern nur die Kombination von zwei bereits bekannten Aussagen). Gib explizit eine Reduktionsfunktion an, die in P-Zeit aus einem Graphen \(G\) eine Formel \(F\) berechnet mit \(F\in 3\textsf{COL}\iff G\in\textsf{SAT}\). Hinweis: für jeden Knoten 3 Variablen.
Motivation: \(L\in\textsf{NPc}\) bedeutet \(L\in\textsf{NP}\wedge \forall L'\in\textsf{NP}:L'\le_{\textsf{P}}L\)
es gibt derzeit keinen effizienten Algorithmus für \(L\)
(sonst auch für SAT, und das wäre eine Sensation)
es hat auch wenig Sinn, einen solchen zu suchen
besser: Aufgabenstellung einschränken o. variieren
Informatiker muß deswegen \(L\in\textsf{NPc}\) schnell erkennen, um sinnlose Arbeit zu vermeiden.
\(L\in\textsf{NP}\) ist meist offensichtlich,
statt \(\forall L'\in\textsf{NP}:\dots\) reicht ein \(L'\in\textsf{NPc}\) (warum?)
deswegen braucht man Beispiel-Probleme aus \(\textsf{NPc}\)
Def: Menge \(M\) heißt Knoten-Überdeckung von \(G=(V,E)\) \(\iff M\subseteq V\wedge \forall e\in E:\exists v\in M: v\in e\)
(\(M\) ist Menge von Knoten, die jede Kante überdeckt)
Def: \(\textsf{VC}=\{(G,k)\mid \exists M:\) \(M\) ist Knotenüberdeckung von \(G\) \(\wedge |M|\le k\}\)
Satz: \(\textsf{VC}\in\textsf{NPc}\)
Beweis: \(\textsf{VC}\in\textsf{NP}\) ist klar (Orakel liefert \(M\))
zeigen \(3\textsf{SAT}\le_{\textsf{P}}\textsf{VC}\)
(\(K_2\) für jede Variable, \(K_3\) für jede Klausel)
Ü: ist die 3 hier wirklich nötig?
Def: Menge \(M\) heißt Kanten-Überdeckung von \(G=(V,E)\) \(\iff M\subseteq E\wedge \forall v\in V:\exists e\in M: v\in e\)
(\(M\) ist Menge von Kanten, die jeden Knoten überdeckt)
Def: \(\textsf{EC}=\{(G,k)\mid \exists M:\) \(M\) ist Kantenüberdeckung von \(G\) \(\wedge |M|\le k\}\)
Satz: \(\textsf{EC}\in\textsf{P}\)
Beweis: evtl. Übung
Satz: \(3\textsf{COL}\in\textsf{NPc}\)
Beweis: \(3\textsf{SAT}\le_{\textsf{P}}3\textsf{COL}\)
eine \(K_3\) \(\{0,\text{Falsch},\text{Wahr}\}\)
für jede Variable \(v\) ein \(K_3\) : \(\{v, \neg v, 0\}\)
für jede Klausel \(l_1\vee l_2\vee l_3\): 6 Knoten \(K_3 - K_3\),
4 Endpunkte verbunden mit \(l_1,l_2,l_3,\text{Falsch}\)
Lemma: in jeder konfliktfreien 3-Färbung:
die Nachbarn der vier Endpunkte des \(K_3-K_3\)
haben nicht die gleiche Farbe.
vgl. mit Ü: \(3\textsf{COL}\le_{\textsf{P}}\textsf{SAT}\)
Ü: Def: \(\textsf{COL}=\{(G,k)\mid G\in k\textsf{COL}\}\), Satz: \(\textsf{COL}\in\textsf{NPc}\)
Definition:
Instanz: Zahlen \(a_1,\ldots,a_n, b\in\mathbb{N}\)
Lösung: Teilmenge \(I\subseteq\{1,\ldots,n\}\) mit \(b=\sum_{i\in I}x_i\)
Satz: \(\textsf{Knapsack}\in\textsf{NPc}\), Beweis: \(3\textsf{SAT}\le_{\textsf{P}}\textsf{Knapsack}\)
Konstruktion: \(F\) mit \(n\) Variablen, \(m\) Klauseln,
für \(x\in \{a_1,\dots,b\}:\text{decimal}(x)\in\{0,1,\dots,4\}^*\),
\(\text{decimal}(b)=4^m 1^n\)
Gewichte \(a_i\) für: positive Vorkommen von Variable in Klausel, negative Vorkommen, Zusatzgewichte
Überträge kommen nach Konstruktion nicht vor
Satz: \(\textsf{HC}\in\textsf{NPc}\)
Beweis: \(\textsf{VC}\le_{\textsf{P}}\textsf{HC}\)
(travelling salesperson)
Formulierung als eingeschränktes Optimierungsproblem:
Instanz: Matrix \(D\in\mathbb{N}^{n\times n}\), Schranke \(K\in\mathbb{N}\)
Lösung: Permutation \(p\) von \([1,\ldots,n]\) (Rundreise)
Maß: \(c(D,p)=\sum_{i=1}^n D(p(i),p((i \bmod n)+1))\)
Formulierung als Sprache (Entscheidungsproblem):
\(\textsf{TSP}=\{(D,K)\mid \exists \text{Permutation} ~ p: c(p,D)\le K \}\)
Satz: \(\textsf{TSP}\in\textsf{NPc}\)
Beweis: \(\textsf{HC}\le_{\textsf{P}}\textsf{TSP}\)
Ü: weitere Optimierungsprobleme http://www.nada.kth.se/~viggo/problemlist/compendium.html
Def: \(R_0:=\) reguläre Ausdrücke mit: Buchstabe, Verkettung, Vereinigung (kein Stern)
Def: \(\textsf{SRI}=\{ (X,Y) \mid X,Y\in R_0\wedge \textsf{Lang}(X)\neq\textsf{Lang}(Y)\)
Ü: \(\textsf{SRI}\in\textsf{NP}\)
Clique, Subgraph Isomorphism, Graph Isomorphism
\(\textsf{VC}\in\textsf{NPc}\)
zeige: planar 3COL \(\in\textsf{NPc}\) mittels \(3\textsf{COL}\le_{\textsf{P}}\text{planar} 3\textsf{COL}\)
Dazu jede Kreuzung von zwei Kanten durch einen geeigneten Teilgraphen ersetzen.
Dominating Set:
\(M\subseteq V\) ist dominierende Menge in \(G=(V,E)\),
falls \(\forall v \in V\setminus M:\exists u\in M: vu\in E\)
\(\textsf{DS}:=\{(G,k)\mid\exists M: |M|\le k\wedge\) \(M\) ist dominierend in \(G\) \(\}\)
zeige durch Beispiel, daß \(\textsf{DS}\neq\textsf{VC}\) und \(\textsf{DS}\neq\textsf{EC}\)
Zeige \(\textsf{DS}\in\textsf{NPc}\) durch geeignete Reduktion
Edge Cover (EC) \(\in \textsf{P}\)
Berechnungsmodelle
Goto, While, Loop, Markov, Turing
konkrete und abstrakte Sytax, Semantik (Interpreter), Äquivalenzen (Compiler)
Berechenbarkeit
REC, \(\phi_x(y)\), \(K\), \(K_0\), Rice, PCP, RE, \(\le_m\), Vollständigkeit
Komplexität
Nichtdeterminismus, Zeit, Platz, P, NP, \(\le_{\textsf{P}}\), NPc
SAT, COL, VC
Verfahren:
Aufzählung einer Menge von Funktionen \(F=\{f_0, f_1,\ldots\}\)
modifizierte Diagonalfunktion \(d':x\mapsto \text{change}(f_x(x))\),
\(d'\in F \Rightarrow \exists i: d'=f_i \Rightarrow d'(i)=\text{change}(f_i(i)) \stackrel{?}{=}f_i(i)=d'(i)\)
Übung/Wiederholung: wende an für \(F =\dots\)
alle Funktionen \(\mathbb{N}\to\mathbb{N}\)
alle Polynome
alle totale berechenbaren Funktionen \(\mathbb{N}\to\mathbb{N}\)
alle partiellen berechenbaren Funktionen \(\mathbb{N}\hookrightarrow\mathbb{N}\)
alle primitiv rekursiven Funktionen
alle in \(\textsf{DTIME}(f)\) berechenbaren Funktionen
Verfahren:
zähle \(\mathbb{N}^2\) auf in Reihenfolge monoton steigender \(C(x,y)\).
(Wdhlg.) Anwendungen:
\(M\in\operatorname{RE}\iff \exists x: M=\dom(\phi_x)\)
\(\{x\mid W_x\) ist unendlich \(\} \le_m \{x\mid W_x =\mathbb{N}\}\)
Platz-Schranken (oberhalb von \(\textsf{P}\), schwere Suchprobleme)
Schaltkreise (unterhalb von \(\textsf{P}\), parallele Algorithmen)
probabilistische Maschinen BPP (mit beschränkter Fehlerhäufigkeit) (kann Prob-\(\textsf{P}\) mehr als \(\textsf{P}\)?)
Quanten-Computer (BQP) (Beziehung zu NP?)
Kryptografie (z.B. zero-knowledge proofs)
implizite Komplexität von Programmen (syntaktische oder andere statische Bedingungen (Typen) \(\textsf{P}\))
Dexter Kozen: Theory of Computation, Springer 2006
S. Arora, B.Barak: Computational Complexity, CUP 2009
Scott Aaronson:
wir messen den Platz nur auf dem Arbeitsband
(nicht Eingabe-, nicht Ausgabe-band)
für \(f:\mathbb{N}\to\mathbb{N}\) bezeichnet \(\textsf{DSPACE}_\text{Alg}(f)\) die Menge der DTM \(M\) mit \(\forall x\in\textsf{Lang}_\textsf{Acc}(M)\) \(\iff\) \(M\) akzeptiert \(x\) mit Arbeitsband der Breite \(\le f(|x|)\)
für \(f:\mathbb{N}\to\mathbb{N}\) bezeichnet \(\textsf{DSPACE}_\text{Prob}(f)\) die Menge der Sprachen \(L\) mit \(\exists M\in\textsf{DSPACE}_\text{Alg}(f): L=\textsf{Lang}_\textsf{Acc}(M)\)
Abkürzung \(\textsf{DSPACE}=\textsf{DSPACE}_\text{Prob}\)
für Menge \(F\) von Funkt.: \(\textsf{DSPACE}(F)=\bigcup_{f\in F} \textsf{DSPACE}(f)\)
Abkürzung \(\textsf{PSPACE}=\textsf{DSPACE}(\text{poly})\)
(nach unserer Definition der TM) Eingabe ist read-only, Ausgabe ist write-only,
Arbeitsband darf nicht benutzt werden (Breite 0)
einzige Speichermöglichkeit ist Zustand
das sind endliche Automaten mit Ein- und Ausgabe
andere Namen dafür: finite (rational) transducer
Bsp: Berechnung des Nachfolgers in Binärdarstellung
\(\textsf{QBF}=\) die Menge der wahren aussagenlogischen Formeln mit Quantoren, ohne freie Variablen
Bsp: welche \(F_i\) sind in QBF?
\(F_1\equiv \forall x\exists y:(x\leftrightarrow\neg y)\), \(F_2\equiv \exists x\forall y\exists z:(x\oplus y\oplus z)\)
Satz: \(\textsf{QBF}\in\textsf{PSPACE}\)
Beweis: Auswertung der Formel rekursiv
z.B. \(\textsf{eval}(\forall x:F) = \textsf{eval}(F[x:=0]) \wedge \textsf{eval}(F[x:=1])\)
benutze Keller (auf Arbeitsband) für die Verwaltung der UP-Aufrufe, die Kellertiefe ist \(\le |F|\)
das Bsp zeigt: die Ressource Platz kann man nachnutzen
…und dabei sehr viel mehr Zeit verbrauchen
\(\textsf{QBF}\) für Formeln der Gestalt \(\forall x_1\exists y_1\forall x_2\exists y_2 \cdots\forall x_n\exists y_n: P(x_1,y_1,x_2,y_2,\ldots,x_n,y_n)\)
als Zweipersonenspiel: für den ersten Zug von \(x\) gibt es einen Antwortzug für \(y\), so daß für jeden …
und \(P(\cdots)\) beschreibt die Gewinnbedingung
viele andere Zweipersonenspiele \(\in \textsf{PSPACE}\)
genauer, das Entscheidungsproblem \(\{s \mid \text{Position\)s\(ist sicherer Gewinn für Spieler 2}\}\)
wenn die Länge des Spiels polynomiell beschränkt ist
Bsp: Stefan Reisch, HEX ist PSPACE-vollständig, Acta Inf. 15(2)1981, 167–191
Satz: \(\textsf{DTIME}(f)\subseteq\textsf{DSPACE}(f)\). Beweis: klar.
Satz: \(\textsf{DSPACE}(f)\subseteq\textsf{DTIME}(2^{O(f)})\)
(dabei \(2^{O(f)} := \bigcup_{c>0} (n\mapsto 2^{c\cdot f(n)}\))
Beweis: sei \(M\in\textsf{DSPACE}_\text{Alg}(f)\).
wenn \(M(x)\) mit \(f(|x|)\) Platz akzeptiert,
dann sind alle Konfigurationen verschieden (sonst \(\bot\)),
es gibt \(\le |\Sigma|^{f(|x|)} = 2^{\log_2 |\Sigma| f(|x|)}\) Konfigurationen
also höchstens so viele Schritte.
Folgerung: \(f\) berechenbar \(\Rightarrow\) \(\textsf{DSPACE}(f)\subseteq \operatorname{REC}\)
Beweis \(\textsf{DSPACE}(f)\subseteq \textsf{DTIME}(2^{O(f)})\subseteq \operatorname{REC}\)
Folgerung: \(\textsf{DSPACE}(\log)\subseteq P\), \(\textsf{PSPACE}\subseteq \textsf{DEXPTIME}\)
Def. \(\le_{\textsf{P}}\) wie gehabt
Satz: \(\textsf{PSPACE}\) ist abgeschlossen bzgl. \(\le_{\textsf{P}}\):
\(\forall L_1,L_2: L_1\le_{\textsf{P}}L_2 \wedge L_2\in\textsf{PSPACE}\Rightarrow L_1\in\textsf{PSPACE}\)
Beweis: Reduktionsfunktion \(f\) ist in polynomieller Zeit, also in polynomiellem Platz berechenbar.
Def: \(L\) ist PSPACE-vollständig, gdw. \(L\in\textsf{PSPACE}\wedge\forall L'\in\textsf{PSPACE}: L'\le_{\textsf{P}}L\)
Satz: \(\textsf{QBF}\) ist PSPACE-vollständig.
Beweis (folgt)
Def: \(\textsf{NSPACE}(f)\) : Probleme lösbar durch nichtdeterministische TM mit Arbeitsband \(\le f(|\text{Eingabe}|)\)
Satz \(\textsf{DSPACE}(f)\subseteq \textsf{NSPACE}(f)\). (ist trivial)
Satz (Savitch) \(\textsf{NSPACE}(f)\subseteq \textsf{DSPACE}(f^2)\).
Beweis (Idee): es ist \(I(x)\to_M^{\le 2^{c\cdot f(|x|)}} F\) zu entscheiden.
verwende UP mit Spez. \(R(x,e,y) \iff x\to_M^{\le 2^e}y\) :
\(R(x,0,y) := x\to_M^{0,1} = (x=y) \vee (x\to_M y)\)
\(R(x,e+1,y) := \bigvee_{h\in\text{Config}} (R(x,e,h)\wedge R(h,e,y))\).
mit Nachnutzung des Platzes. Kellertiefe ist \(\le f(|x|)\), jeder Eintrag im Keller ist \(\le f(|x|)\), Keller braucht Platz \(\le f(|x|)^2\)
Bemerkung: gilt nur für platzkonstruierbare \(f\in\Omega(\log)\)
Folgerung \(\textsf{DSPACE}(\text{poly})=\textsf{NSPACE}(\text{poly})=\textsf{PSPACE}\)
noch zu zeigen: \(L\in\textsf{PSPACE}\Rightarrow L\le_{\textsf{P}}\textsf{QBF}\).
sei \(M\) eine PSPACE-Maschine für \(L\),
benutze Formel von vorhin
\(R(x,e+1,y) := \bigvee_{h\in\text{Config}} (R(x,e,h)\wedge R(h,e,y))\).
äquivalent:
\(R(x,e+1,y) := \exists h \forall a,b: ((a=x\wedge b=h)\vee \dots)\Rightarrow R(a,e,b)\)
damit erhält man eine Formel
der Größe \(\le \log_2(|\Sigma|^{\text{poly}(|x|)})\), also polynomiell in \(|x|\)
diese ist wahr gdw. \(M\) akzeptiert Eingabe \(x\).
\(M\in\textsf{PSPACE}\) akzeptiert \(x\)
\(\iff\) es gibt eine passende Konfigurationsfolge.
Platz für jede Konf. \(\le f(|x|)\) mit \(f\in\text{poly}\), Länge \(\le 2^{O(f)}\)
Konf. kann auch die Anordnung von Spielsteinen auf einem (beschränkten) Brett sein
Übergang \(=\) Spielzug \(=\) (z.B.) Verschieben von Steinen
Joseph C. Culberson: Sokoban is PSPACE-complete, 1997 , http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.41
\(\textsf{Sokoban}\in\textsf{PSPACE}\) ist leicht, Vollständigkeit ist schwer.
Rush Hour ist PSPACE-vollständig. Lunar Lockout auch?
aus bisherigen Betrachtungen folgt:
\(\textsf{L}\subseteq \textsf{NL}\subseteq \textsf{P}\subseteq \textsf{NP}\subseteq \textsf{PSPACE}\subseteq \textsf{EXP}\subseteq \textsf{NEXP}\)
(dabei \(\textsf{L}=\textsf{DSPACE}(\log)\), \(\textsf{EXP}=\textsf{DTIME}(\exp)\))
es ist anzunehmen, daß alle Inklusionen echt sind
aber zeigen kann man derzeit nur
\(\textsf{L}\subset \textsf{PSPACE}\), \(\textsf{P}\subset \textsf{EXP}\)
durch Platz- und Zeithierarchiesätze
Def. zeit-beschränktes Halteproblem
\(K_f := \{(x,y) \mid \phi_x(y) \text{akzeptiert in} \le f(|y|) \text{Schritten}\}\)
Satz: \(K_f\in\textsf{DTIME}(f^3)\). Beweis: Simulation durch eine Maschine \(S\) mit zwei Bändern (eines für \(x\), anderes als Arbeitsband für \(\phi_x\))
Satz: \(K_f\notin\textsf{DTIME}(f/2)\). Beweis (indirekt). Falls \(K_f\) entschieden durch \(M\), dann betrachte Programm \(P: x\mapsto \neg M(x,x)\) und Aufruf \(P(P)\).
Folgerung \(\textsf{DTIME}(f)\subset\textsf{DTIME}((2f)^3)\).
Folgerung \(\textsf{PTIME}\subset \text{EXPTIME}\)
Bew: \(K_f\) für \(f=(n\mapsto 2^n)\).
\(\textsf{AC}^d,\textsf{NC}^d\): Menge der Entscheidungsprobleme,
die lösbar sind durch Schaltkreise mit Operationen
\(\neg\) sowie \(\wedge, \vee\) (zweistellig: \(\textsf{NC}^d\), mehrstellig: \(\textsf{AC}^d\))
uniform mit Größe \(O(\text{poly})\), Tiefe \(O(\log^d(n))\)
Satz: Parität \(\in\textsf{NC}^1\), Parität \(\notin\textsf{AC}^0\)
Bsp: Produkt von Relationen (Booleschen Matrizen) \(\in\textsf{AC}^0\), auch \(\in \textsf{NC}^1\)
Bsp: reflexiv-transitive Hülle \(\in \textsf{AC}^1\), auch \(\in\textsf{NC}^2\)
Satz: \(\forall d \ge 0: \textsf{NC}^d\subseteq \textsf{AC}^d \subseteq \textsf{NC}^{d+1}\)
Def: \(\textsf{NC}:= \bigcup_{d\ge 0} \textsf{NC}^d\), \(\textsf{AC}:= \bigcup_{d\ge 0} \textsf{AC}^d\).
Satz: \(\textsf{NL}\subseteq\textsf{NC}= \textsf{AC}\subseteq \textsf{P}\). Beweise:
\(\textsf{NC}=\textsf{AC}\): wg. vorigem Satz
\(\textsf{NL}\subseteq\textsf{AC}\): refl-tr. Hülle der Übergangsrelation
(auf \(\exp(c\cdot \log |x|) = \text{poly}(|x|)\) vielen Zuständen)
\(\textsf{AC}\subseteq \textsf{P}\): Schaltkreis-Auswertung schichtweise
Def: \(A \operatorname{\le_{\textsf{L}}}B\) falls \(\exists f\in\textsf{FSPACE}(\log): \forall x: x\in A\iff f(x)\in B\)
Satz: \(\operatorname{\le_{\textsf{L}}}\) ist transitiv.
Beweis — Vorsicht: \(g(f(x))\) naiv benötigt zuviel Platz!
Satz: \(A\operatorname{\le_{\textsf{L}}}B\wedge B\in\textsf{NC}\Rightarrow A\in\textsf{NC}\)
Satz: \(A\operatorname{\le_{\textsf{L}}}B\wedge B\in\textsf{P}\Rightarrow A\in\textsf{P}\)
Def: \(B\) heißt \(\textsf{P}\)-vollständig: \(B\in\textsf{P}\wedge\forall A\in\textsf{P}:A\operatorname{\le_{\textsf{L}}}B\).
Satz: Schaltkreisauswertung ist \(\textsf{P}\)-vollständig.
Modellierung für parallele Komplexität:
\(\textsf{NC}\): Aufgaben mit gut parallelisierbarer Lösung
\(\operatorname{\le_{\textsf{L}}}\): Reduktion, die Parallelisierbarkeit erhält
\(\textsf{P}\)-vollständig: keine gute parallelen Alg. bekannt,
KW 46: Einführung, GOTO-Programme
KW 47: WHILE-Programme, LOOP-Programme
KW 48: universelle Programme, Halteproblem, Satz v. Rice
KW 49: REC, RE, \(\le_m\)
KW 50: Turingmaschinen, Markov-Algorithmen, Wortersetzung
KW 51: Unentscheidbare Eigensch. von Grammatiken, in der Logik
KW 54: Nichtdeterminismus/Orakel, Komplexitätstheorie, P, NP
KW 55: \(\le_P\), NP-vollständige Probleme
KW 56: Zusammenfassung, Ausblick