4-platzkomplexitaet.tex

%!TEX root = 0-main.tex

% Author: Philipp Moers <soziflip@gmail.com>



\datum{26.11.15}

\chapter{Platzkomplexität} % (fold)
\label{cha:platzkomplexitaet}




\section{Platzkonstruierbare Funktionen}


\begin{definition}

    Eine Funktion $s(n)$ heißt \definiere{platzkonstruierbar} genau dann, wenn eine deterministische Turingmaschine existiert, die bei Eingabe $0^n$ genau $s(n)$ Bandfelder beschreibt und dann hält.

\end{definition}

\begin{beispiel}

    Alle Polynome mit Koeffizienten $\in \Q^+$, die Wurzelfunktion, die Logarithmus-Funktion, die Potzenfunktion usw. sind platzkonstruierbar.

\end{beispiel}




\section{Platzverbrauch einer Turingmaschine}

\begin{definition}

    Der \definiere{Platzverbrauch einer Turingmaschine} (deterministisch oder nichtdeterministisch) bei Eingabe $x$ ist

    \begin{itemize}

        \item \textbf{erste Definition}\\
        die Größe des beschriebenen Teils aller Bänder am Ende der Berechnung. (Mit dieser Definition ist der Platzverbrauch stets $\geq |x|$).

        \item \textbf{zweite Definition}\\
        die Endgröße aller anderen Bänder, wobei das Eingabeband nicht überschrieben werden darf.

    \end{itemize}

    Die zweite Definition ist Standard,w enn sublineare Platzschranken betrachtet werden, zum Beispiel $\log(n)$. Oberhalb von $\bigO(n)$ sind die beiden Definitionen äquivalent.



    Notation: $DSPACE_M (x)$ und $NSPACE_M (x)$

    $DSPACE_M (s(n)) = \{   L  \ |\   \exists DTM M : L = L(M) \land DSPACE_M(x) = \bigO(s(|x|)) \}$

    $NSPACE_M (s(n)) = \{   L  \ |\   \exists DTM M : L = L(M) \land NSPACE_M(x) = \bigO(s(|x|)) \}$

    $PSPACE = \bigcup_{k \geq 0} DSPACE(n^k) $ (polynomieller Platz)

    $LINSPACE = DSPACE(n)$

    $LOGSPACE = DSPACE(\log n)$ (auch als $L$ bezeichnet)

    $NLOGSPACE = NSPACE(\log n)$ (auch als $NL$ bezeichnet)


\end{definition}


\begin{beispiel}

    STCONN (Erreichbarkeit in gerichteten Graphen) ist $\in NLOGSPACE$ (rate Pfad) und $\in LINSPACE$ (Tiefensuche/Breitensuche)

\end{beispiel}


Es gibt eine triviale, aber wissenswerte Beziehung zwischen Zeit- und Platzkomplexität:

% $$ NSPACE(s(n)) \subseteq DTIME (2^{\bigO(s(n))}) $$      % not sure
$$ DSPACE(s(n)) \subseteq DTIME (2^{\bigO(s(n))}) $$

% Alle Berechnungsfolgen können aufgezählt werden.
Hat die Berechnung nach $2^{c*s(n)}$ Schritten nicht geendet, so kann abgebrochen werden wegen Wiederholung einer globalen Konfiguration. (Tatsächlicher Platzverbrauch $\leq c * s(n)$)



$$ DTIME(t(n)) \subseteq DSPACE (t(n)) $$

Mehr Platz als Laufzeit kann nicht angefordert werden.





\begin{satz}

    Für deterministische Einband-Turingmaschinen $T$ gilt:

    $DTIME_T(x) = \bigO(t(|x|) \Longrightarrow  L(T) \in DSPACE(\sqrt{t(n)})$


\end{satz}

Für Mehrband-Turingmaschinen gibt es einen ähnliches Satz, bei dem der Platz allerdings etwas größer ist. Dass er für Einband-Turingmaschinen so gut ist, ist gewissermaßen kurios.





\section{Platzhierarchiesatz}

\begin{satz}

    ``Echt mehr Platz hilft auch mehr.''

    \textit{Für genaue Aussage und Beweis siehe z.B. Papadimitrion}
\end{satz}

Wichtige Konsequenz:

$$ LOGSPACE \subset PSPACE $$

$$ LOGSPACE \subseteq NLOGSPACE \subseteq \ComplexityClassP \subseteq \ComplexityClassNP \subseteq PH \subseteq PSPACE \subseteq \ComplexityClassEXP$$

Von jeder dieser Inklusionen ist unbekannt, ob sie echt sind. Mindestens eine muss aber echt sein.






\section{Zusammenhänge von Platzkomplexitätsklassen}


\begin{satz}

    \definiere{Satz von Savitch}

    Für eine platzkonstruierbare Funktion $s(n) \geq \log(n)$ ist \\
    $ NSPACE(s(n)) \subseteq DSPACE(s(n)^2)$

    (Vergleiche
    $ NTIME(t(n)) \subseteq DTIME(2^{\bigO(t(n))})$
    )

\end{satz}

\begin{beweis}

    Sei eine nichtdeterministische Turingmaschine $T$ gegeben mit Platzbedarf $S = c * s(|x|)$ bei Eingabe $x$. Wir betrachten eine Kodierung der globalen Konfigurationen von $T(x)$ durch Wörter der Länge $S$ und o.\,B.\,d.\,A. gebe es exakt eine akzeptierende Endkonfiguration $s_{ACC}$. (Alle Bänder am Ende löschen, d.h. mit $0$ überschreiben.)

    $
    x \in L(T)
        \Longleftrightarrow
    s_{ACC} \text{ von } s_{INI} \text{ aus in } \leq 2^S \text{ Schritten erreichbar}
    $

    Hier steht $s_{INI}$ für die Startkonfiguration bei Eingabe $x$. $2^S$ ist die Gesamtzahl der Konfigurationen.

    Das heißt $s_{ACC}$ ist von $s_{INI}$ aus im Graphen der Konfigurationen erreichbar (Spezialfall von STCONN).

\end{beweis}


\textbf{Notation:}

$s \rightarrow_T s'$: $s'$ ist 1-Schritt-Folgekonfiguration von $s$ in $T$ und kann in $LOGSPACE$ entschieden werden.

$REACH(s, s')$: $s \rightarrow^\ast s'$ ($s'$ ist von $s$ erreichbar)

$REACH(s, s', i)$: $s \rightarrow^{\leq 2^i} s'$ ($s'$ ist von $s$ in weniger als $2^i$ Schritten erreichbar)


$ x \in L(T) \Longleftrightarrow REACH(s_{INI}, s_{ACC}, S)$

Es gilt
$$REACH(s, s', 0) \Longleftrightarrow s = s' \lor s \rightarrow_T s'$$
\hspace{4cm}($2^0 = 1$)
$$REACH(s, s', i+1) \Longleftrightarrow \exists \check{s} : REACH(s, \check{s}, i) \land REACH(\check{s}, s', i)$$
\hspace{4cm}($2^{i+1} = 2 * 2^i$)\\
Dies liefert eine rekursive Implementierung von $REACH(s,s',i)$ \\
\hspace{4cm}($\exists \check{s} \leadsto \text { for } \check{s} \in \text{ globale Konfigurationen}$)


Der Rekursionsstack hat Tiefe $S$ (Toplevel-Aufruf $REACH(s_{INI}, s_{ACC}, S)$).
\\
Jeder Activationrecord hat Größe $\bigO(S)$ genauer gesagt $2 S$ für die beiden Parameter $s, s', \log(S)$ für die Parameter $i$. Wenn gewünscht noch ein weiteres $S$ für die for-Schleife.


Die Gesamtgröße des Stacks ist beschränkt durch $S * \bigO(S) = \bigO(S^2)$.


Historisch wurde zunächst gezeigt, dass STCONN in $DSPACE(\log(n)^2)$ liegt. Der Satz von Savitch kann auch hieraus abgeleitet werden.









\datum{30.11.15}




\begin{satz}

    \definiere{Satz von Immerman-Szelepcsényi}

    Sei $s(n) \geq \log(n)$.

    Dann ist $NSPACE(s(n)) = co\text{--}NSPACE(s(n))$

    Wichtiger Spezialfall: $co\text{--}STCONN \in NSPACE(\log(n)) = NL = NLOGSPACE$
    \\
    Die allgemeine Behauptung kann aus diesem Spezialfall leicht gefolgert werden (durch den Graph der globalen Konfiguration).


\end{satz}

\begin{beweis}

    Es sei eine nichtdeterministische Turingmaschine $T$ vorgelegt und $NSPACE_T(x) \leq c * s(|x|)$. Wir müssen eine nichtdeterministische Turingmaschine $T'$ konstruieren, sodass $NSPACE_{T'}(x) = \bigO(s(|x|))$ und $x \in L(T') \Leftrightarrow x \notin L(T)$.
    \\
    Es existiert akzeptierende Berechnung von $T'$ auf x genau dann, wenn alle Berechnungen von $T$ auf $x$ verwerfen.

    Sei $x$ fixiert und o.\,B.\,d.\,A. $\Sigma = \{0,1\}$.
    \\
    Schreibe $S_{INI}$ für die globale Startkonfiguration von $T$ auf $x$
    und $S_{ACC}$ für die (o.\,B.\,d.\,A.. einzige) akzeptierende globale Konfiguration.
    Weiter sei $S = c' *  s(|x|)$ so gewählt, dass alle globalen Konfigurationen durch $0/1$-Strings der Länge $S$ kodiert werden.
    \\
    $s \rightarrow_T s'$ bedeute, dass $s'$ in einem Schritt aus $s$ hervorgehen kann (Das kann in Platz $\log(S)$ entschieden werden).
    \\
    $T'$ soll nun $x$ akzeptieren genau dann, wenn kein Pfad (der Länge $2^S$) von $s_{INI}$ zu $s_{ACC}$ existiert.
    (Anzahl der globalen Konfigurationen ist kleiner als $2^S$. Ein einziger Pfad braucht, wenn er voll ausgeschrieben wird, schon Platz $S * 2^S \notin \bigO(s(|x|))$.)

    \textbf{Vorbemerkung:}\\
    Nehmen wir an, dass die Anzahl $N$ der von $s_{INI}$ aus erreichbaren globalen Konfigurationen bekannt ist bzw. berechnet werden kann.

    Wir zählen der Reihe nach alle globalen Konfigurationen auf (geht mit Platz $\bigO(S)$) und raten für jede von denen einen Pfad von $S_{INI}$ dorthin. Durch Mitführen eines Zählers haben wir am Ende der Aufzählung die Anzahl derjenigen Knoten, für die das gelungen ist.

    \begin{codebox}[javascript]
function A(...) {
    cnt = 0;
    for (s in globalConfigs) {
        pfad = guessPath();
        if (pfad.endsAt(s))
            cnt++;
        if (s = s_acc)
            return "reject";
    }
    if (cnt == N)
        return "accept";
    else
        return "reject";
}

function guessPath() {
    s = s_ini;
    for (i = 1; i <= 2^S; i++) {
        sX = guessNonDet({0,1}^S);
        if (s2 -> sX) {
            s2 = sX;
        } else {
            return "reject";
        }
        b = guessNonDet({0,1});
        if (b) {
            break;
        }
    }
}
    \end{codebox}

    Falls $N$ die Anzahl der von $s_{INI}$ aus erreichbaren globalen Konfigurationen ist, so \underline{kann} A akzeptieren genau dann, wenn $s_{ACC}$ von $s_{INI}$ unerreichbar ist.
    \\
    Begründung ``$\Rightarrow$'': Falls A akzeptiert, dann ist $s_{ACC}$ tatsächlich unerreichbar, weil alle $N$ erreichbaren Konfigurationen in der for-Schleife als solche erkannt wurden und $s_{ACC}$ nicht unter ihnen war.
    \\
    Begründung ``$\Leftarrow$'': Falls $s_{ACC}$ unerreichbar ist, so kann A akzeptieren, indem bei jedem der von $s_{INI}$ aus erreichbaren s tatsächlich ein entsprechender Pfad geraten wird.


    Grobe Struktur des Algorithmus für $T'$:
    \begin{codebox}[javascript]
N = 1;
for (i = 1 ... 2^S) {
    // Invariante: Anzahl der von s_ini aus in weniger als i-1 Schritten erreichbaren Konfigurationen ist gleich N
    updateN();
}
A();
    \end{codebox}
    Der Block \codeline{updateN()} wird selbst Nichtdeterminismus enthalten, in dem Sinne, dass die gesamte Berechnung verwerfend abgebrochen werden kann. Passiert das nicht, dann ist $N$ korrekt aktualisiert und bei passender Wahl der nichtdeterministischen Entscheidungen, passiert das auch.

    \begin{codebox}[javascript]
function updateN() {
    cnt = 0;
    for (s in globalConfigs) {
        reachable = false;
        cnt2 = 0;
        // alle N Stück die von s_ini aus in weniger als i-1 Schritten erreichbar sind, aufzählen
        for (sCheck in globalConfigs) {
            pfad = guessPath();
            if (pfad.endsAt(sCheck)) {
                cnt2++;
                if (sCheck == s || sCheck -> s)
                    reachable = true;
            }
        }
        if (cnt2 != N)
            return "reject";
        else if (reachable)
            cnt++;
    }
    N = cnt;
}
    \end{codebox}

    Am Ende von \codeline{updateN} hat entweder N den korrekten Wert oder es wurde verworfen.
    Es ist möglich, die nichtdeterministischen Entscheidungen so zu treffen, dass der korrekte Wert geliefert wird, sodass nicht verworfen wird.


\end{beweis}










\datum{03.12.15}



\section{Noch ein Satz von Cook}


\begin{definition}

    $NSPACE(s(n)) + STACK$

    Intuitiv ist das alles, was mit $\bigO(s(n))$ platzbeschränkten Arbeitsbändern und einem unbeschränkten Stack berechnet werden kann.

    Eine mögliche Formalisierung: Turingmaschine mit Stack hat zusätzlich ein Stackalphabet $\Gamma$ und ein besonderes Symbol $A \in \Gamma$. Jedes ``Quintupel'' enthält eine zusätzliche Komponente, die Stack-Aktion, eine der folgenden drei:
    \begin{itemize}
        \item IDLE (Keller bleibt unverändert)
        \item POP (oberstes Kellersymbol wird entfernt)
        \item PUSH ($x \in \Gamma$ auf den Keller legen)
    \end{itemize}
    Außerdem ist das jeweils oberste Kellersymbol lesbar.
    \\
    Die Maschine wird mit Kellerinhalt $\bigAoverlinesqcup$ gestartet und hält per Definition, wenn der Keller leer wird, d.h. wenn $A$ gePOPt wird.

    Formal:
    \\
    $\delta = Q \times (\Sigma^k \times \Gamma) \times Q \times \Sigma^k \times S$
    \\
    wobei $S$ die Menge der Stack-Aktionen ist.


\end{definition}


\begin{beispiel}

    Der Beweis des Satzes von Savitch zeigt, dass STCONN $\in DSPACE(\log(n) + STACK)$ und $NSPACE(s(n)) \subseteq DSPACE(s(n) + STACK)$ ist.



\end{beispiel}



\begin{satz}

    $s(n) \geq \log(n) \Longrightarrow NSPACE(s(n)) + STACK = DTIME(2^{\bigO(s(n))})$

\end{satz}

\begin{beweis}

    \begin{itemize}

        \item ``$\subseteq$'':

        Sei $T$ eine zunächst deterministische durch $s(n)$ platzbeschränkte Turingmaschine mit Stack.
        \\
        Wir fixieren eine Kodierung der ``Bandkonfigurationen'' von $T$. Diese Bandkonfigurationen beinhalten den Zustand und gesamten Inhalt aller Arbeitsbändern und Kopfpositionen. Bei Eingabe der Größe $n$ haben die so kodierten Bandkonfigurationen die Größe $\bigO(s(n))$, also konkret $c * s(n)$ für ein festes $c$.
        \\
        Sei nun eine Eingabe fixiert. $B$ sei die Menge der Bandkonfigurationen der Größe $c * s(|x|)$ und $\Gamma$ das Stackalphabet.
        \\
        Wir definieren die partielle Funktion $f: B \times \Gamma \longrightarrow B: f(b, x) = b'$
        \\
        $b'$ ist die Bandkonfiguration, die erreicht wird, wenn man $T$ in $b$ und mit Kellerinhalt $\bigxsqcup$ startet und so lange rechnet, bis $X$ zum ersten Mal gePOPt wird.


        \textbf{Bemerkung:}\\
        $x \in L(T) \Longleftrightarrow f(b_{INI}, A) = b'$ und $b'$ akzeptierende Endkonfiguration ist. o.\,B.\,d.\,A. ist $b'$ eindeutig.

        \textbf{Bemerkung:}\\
        Streng genommen sollte man schreiben $f_x(b, X)$ oder $f(x, b, X)$, da die Eingabe $x$ in die Definition von $f$ einfließt.

        $f$ gestattet folgende rekursive Definition:

        $f(b, X) =
        \begin{cases}
        b'                  & , \text{POP}     \\
        f(b', X)            & , \text{IDLE}   \\
        f(f(b', Y), X)      & , \text{PUSH(Y)}
        \end{cases}
        $

        wobei $b'$ die auf $(b,X)$ unmittelbar folgende Bandkonfiguration ist.

        Statt nun $f(b_{INI}, A)$ durch Rewriting auszuwerten, was letztendlich der Berechnung von $T$ entspräche, tabulieren wir die gesamten $f$-Werte systematisch mit dynamischer Programmierung. Die Anzahl der Bandkonfigurationen ist $2^{c*s(|x|)}$. Damit gibt es ingesamt $\bigO(2^{c*s(|x|)})$, o.\,B.\,d.\,A. $2^{c*s(|x|)})$ viele $f$-Aufrufe. Eine Wertetabelle für $f$ kann also in Zeit $2^{\bigO(s(|x|))}$ komplett ausgefüllt werden.
        \\
        Gesamtrechenzeit: $\bigO((2^{c*s(|x|)})^2) = 2^{\bigO(s(|x|))}$


        Wenn die Maschine nichtdeterministisch ist, dann nehmen wir statt $f$ die Funktion $F: B \times \Gamma \times B \longrightarrow bool:\\
        F =
        \begin{cases}
         true        & \text{falls es Berechnung von } b \text{ nach } b' \text{ gibt, an deren Ende } X \text{ erstmals gePOPt wird}       \\
         false       & \text{sonst}     \\
        \end{cases}
        $

        $F$ kann ganz genauso mit dynamischer Programmierung ausgewertet werden.



        Sei umgekehrt $T$ eine deterministische Turingmaschine mit Zeitschranke $2^{c*s(n)}$.
        \\
        Die Kopfpositionen aller Köpfe könenn durch String der Länge $\bigO(s(n))$ kodiert werden (Binärkodierung der numerischen Positionen).
        $a$ mit $|a| = c' * s(n)$ kodiere diese Positionen.
        \\
        Ebenso können Zeitpunkte in der Berechnung durch String dieser Länge kodiert werden.

        Wir definieren bei fester Eingabe $x$ folgende rekursive Funktionen:
        \begin{itemize}
            \item
            $band(t, a) \in \Sigma^k$ als Bandinhalt zur Zeit $t$ an den Positionen $a$.
            \\
            $band(0,   a) = \text{ Inhalt der initialisierten Bänder an den geforderten Positionen }$
            $band(t+1, a) = \dots zustand(t) \dots band(t,a) \dots kopf(t)$

            \item
            $zustand(t) \in Q$
            \\
            $zustand(0) = q_0$

            \item
            $kopf(t)    = \text{ Positionen aller Köpfe zur Zeit } t$
            \\
            $kopf(t+1)  = \dots kopf(t) \dots band(t,a) \dots zustand(t) $

        \end{itemize}

        Die klassische rekursive Auswertung dieser Funktionen
        beziehungsweise des Toplevel-Aufrufs
        $zustand(2^{c*s(|x|)}) \in \{ q_{ACC}, q_{REG} \} $ kann auf
        einer $DSPACE(s(n)) + STACK$ Maschine simuliert werden.

        % TODO der beweis ist noch nicht fertig oder

\end{itemize}


\end{beweis}










\datum{7.12.2015}


\section{Logarithmischer Platz}


Eine Funktion $f: \Sigma^\ast \Rightarrow \Sigma^\ast$ ist in $FL$ und
heißt \definiere{in logarithmischem Platz berechenbar}, wenn es eine
deterministische Turingmaschine gibt die bei Eingabe $x$:

\begin{itemize}
\item Den Funktionswert $f(x)$ auf ein gesondertes Ausgabeband schreibt.
\item Das Ausgabeband nicht mehr ließt.
\item Das Eingabeband (wie immer
bei Space) nicht mehr beschreibt.
\item $\bigO(log|x|)$ platzbeschränkte Arbeitsbänder besitzt.
\end{itemize}

\textbf{Äquivalente Charakterisierung:}
Maschine schreibt das $n$-te Symbol auf
ein besonderes Band (oder signalisiert es durch Einnehmen eines
bestimmten Zustandes), wenn $n$ in Binärkodierung auf ein besonderes
Band geschrieben wird.

\textbf{Bemerkung}\\
\begin{itemize}
\item $2^{c*log(n)}=n^c$
\item $f \in FP \Rightarrow |f(x)| = \bigO(n^c)$
für ein $c$, d.\,h. polynomiell beschränkt und auch $DTIME_T(x) \in \bigO(n^c)$
bei passenden $T$, welches $f$ berechnet.
\end{itemize}

\textbf{Bemerkung}\\
$FL \subseteq FP$
\begin{satz}
    $FL$ ist unter Komposition abgeschlossen.
    $f,g \in FL \Rightarrow g \times f \in FL$
\end{satz}

Gegeben Turingmaschinen $T_f$ und $T_g$ im zweiten Format ($n$-tes Symbol von
$f(x)$ wird bei Eingabe von $x$ und $n$ ``on demand'' berechnet.

Turingmaschine $T_{g \times f}$ für $g \times f $ wird ebenfalls im
2. Format konstruiert. Sie simuliert auf der äußeren Ebene die
Maschine $T_g$.  Jede Leseanfrage der Eingabe wird in eine Berechnung
von $T_f$ auf $x$ an der entsprechenden Ausgabeposition übersetzt.





\section{Mehr Härte und Vollständigkeit}

% \definiere{NL-hart, P-hart, NL-vollständig, P-vollständig}
\begin{itemize}
\item $X$ ist \definiere{NL-hart}, wenn für jedes $X'\in NL$ gilt $X' \leq_L X$
\item $X$ ist \definiere{P-hart}, wenn für jedes $X'\in P$ gilt $X' \leq_L X$
\item $X$ ist \definiere{NL- bzw. P-vollständig}, wenn $X$ NL-hart bzw. P-hart ist und $X\in NL$ bzw. $X\in P$
\end{itemize}

Hierbei bedeutet $X' \leq_L X$, dass $f \in FL$ existiert, mit $x \in X' \Leftrightarrow f(x) \in X$

\textbf{Bemerkung:}\\
$X' \leq_L X \Rightarrow x \leq_P X, \text{ bzw. } X \leq X'$

\begin{satz}
    Das Problem STCONN (Erreichbarkeit im gerichteten Graphen) ist NL-vollständig.
\end{satz}

\begin{beweis}
    $STCON \in NL$ \checkmark

    \textbf{NL-hart:} Sei $T$ eine NL-Maschine. $x \in ((T) E)$
    es existiert ein Pfad von $a_{INI}$ nach $a_{ACC}$ im Graphen, dessen
    Knoten die globale Konfiguration von $T$ bei Eingabe $x$ sind, $a_{INI}$ die
    Startkonfiguration und $a_{ACC}$ die (o.\,B.\,d.\,A. eindeutige) akzeptierende Endkonfiguration ist. Die Übersetzung von $x$ in dem Graphen kann offensichtlich durch eine ``Fl-Maschine'' im 1. Format geschehen.
\end{beweis}





\section{Horn}


\begin{definition}
    Eine Klausel (Disjunktion von Literalen) mit höchstens einem positiven
    Literal heißt \definiere{Hornklausel}. Hornklauseln können logische äquivalent in
    den Formaten:
    %das v ist hier gemeint
    \begin{itemize}
    \item $P_1, P_2, \dots P_k \rightarrow q$
    \item d.\,h. $\neg p_1 \lor \neg p_2 \lor \dots \neg p_k \lor q$
    \item oder $P_1, P_2, \dots P_k \rightarrow \bot$
    \item d.\,h. $\neg p_1 \lor \neg p_2 \lor \dots \neg p_k$
    \end{itemize}
    geschrieben werden.

\end{definition}



\begin{definition}
    Gegeben eine Menge von Hornklauseln $H$.
    Das Problem, ob $H$ unerfüllbar ist, heißt \definiere{Hornproblem}.
\end{definition}

%-----
\begin{definition}
    Eine Hornklausel der Form $\rightarrow q$ k = 0 heißt \definiere{Faktum}.
    Eine Hornklausel der Form $\rightarrow \bot$ k = 0 heißt \definiere{Goal}.
\end{definition}

In der Regel entfällt $H$ genau ein ``Goal'', $p\rightarrow \bot$.
\\
$H$ ist dann unerfüllbar, genau dann, wenn $p$ aus den übrigen Klausen hergeleitet werden kann. $H \vdash p$ hierbei ist die Herleitbarkeit wie folgt definiert.
\begin{itemize}
\item $\rightarrow q \in H$ dann $H+g$ alle Fakten sind herleitbar
\item $P_1, P_2, \dots P_k \rightarrow q \in H$ und
$H+P_1, H+P_2, \dots H+P_k$ dann auch $H+g$
\end{itemize}

\textbf{Bemerkung:}\\
Eine Horn-Klausel Menge ohne Goals ist immer erfüllbar.

\textbf{Bemerkung:}\\
Eine Hornklauselmenge mit mehreren Goals ist unerfüllbar
genau dann, wenn mindestens ein Goal herleibar ist.

\begin{satz}
$Horn \in P$ Wir benutzen eine dynamische Menge $S$, die am Ende alle
herleitbaren Variablen enthalten soll. $S:=\emptyset$
\end{satz}

%Pseudocodes
\begin{codebox}[javascript]
while(!done)
  s' =  s
  for p_1, \dots, p_k  \rightarrow q \in H
    if{p1, \dots, p_k} \seteq S' then
      S' := S' \u {q}
    done := S' = S''; S := S'
return ``es existiert P \rightarrow \bot \in H mit q \subseteq S''
\end{codebox}

Dieses Vorgehen läuft in polynomieller Zeit, da die Zahl der
Durchläufe durch die Zahl der Variablen beschränkt ist, aber nicht
offensichtlich in lmgarithmischem Platz, da die dynamische Menge linearen Platz
benötigt.

\begin{beispiel}
    \begin{itemize}
    \item $ \rightarrow A $
    \item $ A \rightarrow B $
    \item $ F\rightarrow F $
    \item $ B,C \rightarrow D $
    \item $ A,B \rightarrow C $
    \item $ A,D \rightarrow E $
    \item $ E\rightarrow \bot $
    \end{itemize}
    $S:\emptyset ,\{A\},\{A,B\},\{A,B,C\},\{A,B,C,D\},\{A,B,C,D,E\}$
\end{beispiel}

\begin{satz}
    Das Hornproblem ist P-vollständig.
\end{satz}

\begin{beweis}
    Genauo wie Satz Cock(SAT ist NP-vollständig), im Fall einer
    deterministschen Maschine entstehen bei der Übersetzung nur
    Horn-Klauseln.
    \paragraph{Details}
    Sei eine deterministsche Turingmaschine $T$ gegeben, Eingabe $x DTIME_T(x) \subseteq p(|x|)$
    \paragraph{Variablen}
    \begin{description}
    \item[$zust(t,g)$] Zustand zu Zeit $t$ ist $g$
    \item[$band(t,i,x)$] Bandinhalt zur Zeit $t$ an Position $i$ ist
    \item[$kopf(t,i)$] Kopf an Pos $i$ zur Zeit $t$
    \end{description}

    Klauseln z.B.
    \begin{itemize}
    \item $band(t,i,x), kopf(t,i') \rightarrow band(t+1, i,x)$
    \item $band(t,i,x), kopf(t,i), zust(t,q) \rightarrow band(t+1, i, x')$
    \item $band(t,i,x), kopf(t,i)$
    \item $Zustand(t,q) \rightarrow zust(t+1, g')\dots$
    \end{itemize}
    falls jeweils $S(g,x) = (g', x', m)$

    Eingabe $x$ wird akzeptiert genau dann, wenn $zust(P|x|), q_{ACC}$
    herleibar ist um Goal $zust(P(|x|), q_{ACC} \rightarrow \bot$
    hinzunehmen.  Die Übersetzung von $T$, $x$ in diese Klauselmenge kann mit
    FL-Maschine durchgeführt werden. Also $L(T) \leq_{L}$ HORN.
\end{beweis}

Das bereits genannte offene Problem $NL \subsetneq P$ NL echt in $\ComplexityClassP$ enthalten?
kann also umformuliert werden, in die Frage, ob $HORN \in NL$.

\textbf{Markieren von Klauseln}
\\
Auf ein Fakt darf jederzeit eine Marke gelegt werden. Liegen auf allen
Prämissen $p_1, p_2, \dots, p_k$ einer Klausel
$p_1, p_2, \dots, p_k \rightarrow$ schon Marken,
dann darf $q$ mit einer Marke beheftet werden.








\datum{10.12.15}





\section{Quantifizierte Boolesche Formeln}


\begin{satz}
    $QBF$ ist PSPACE-vollständig.

\end{satz}


\definiere{Quantifizierte Boolesche Formeln} ($QBF$)

Gegeben ist eine boolesche Formel mit Quantoren, die über boolesche Werte rangieren.
$$ \forall x \exists y . x \leftrightarrow \neg y  $$
o.\,B.\,d.\,A. kann man diese Formeln als geschlossen voraussetzen (ggf. $\exists$, $\forall$ davorschreiben)
\\
Gesucht ist die Antwort auf die Frage, ob diese Formel wahr ist.



Gegeben ist eine boolesche Formel $\phi$.
$$ \phi \text{ erfüllbar } \Longleftrightarrow \exists x_1 \exists x_2 \dots \exists x_n . \phi \in QBF $$
wobei $\{ x_1 \dots x_n \}$ die Variablen von $\phi$ sind.
\\
$$ TAUT \leq QBF $$
$$ \phi \text{ Tautologie } \Longleftrightarrow \forall x_1 \forall x_2 \dots \forall x_n . \phi \in QBF $$


$AEQSAT = \{ (\phi, \psi) \quad | \quad \phi \text{ erfüllbar } \Leftrightarrow \psi \text{ erfüllbar } \}$
$$(\phi, \psi) \in AEQSAT \Longleftrightarrow (\exists x . \phi ) \Leftrightarrow (\exists y. \psi) \in QBF $$
\\
$$\exists x_1 \exists y_1 \forall x_2 \forall y_2 . (\phi(x_2) \rightarrow \psi(y_1)) \land (\psi(y_2) \rightarrow \phi(x_1))$$





\definiere{Spezialfall: $QBF_n$}

% pränex???
Gegeben ist eine $QBF$-Formel in Pränexform (alle Quantoren ganz außen) mit maximal $n$ Quantorenwechseln beginnend mit $\exists$.

Gegeben: $\exists x_1 \forall x_2 \exists x_3 \dots \exists/\forall x_n . \phi$ wobei $\phi$ eine boolesche Formel ohne Quantoren ist.

$QBF_n$ ist vollständig für $\Sigma_n^P$ (polynomielle Hierarchie) falls $n \geq 1$.
\\
(Lezteres ist unmittelbare Konsequenz aus der logischen Charakterisierung der PH und Satz von Cook.)




Rekursiver Algorithmus für QBF:
\begin{codebox}[javascript]
    check(exists x.phi, eta) =
        check(phi, eta[x -> true]) or
        check(phi, eta[x -> false])
    check(forall x.phi, eta) =
        check(phi, eta[x -> true]) and
        check(phi, eta[x -> false])
    check(phi1 and phi2, eta) =
        check(phi1, eta) and
        check(phi2, eta)
    check(x, eta) = eta(x)
        ...
\end{codebox}



Wi zeigen jetzt $L \leq QBF$ für beliebiges $L \in PSPACE$:

\begin{beweis}

    Sei $T$ eine deterministische Turingmaschine mit $L(T) = L$ und $DSPACE_T(x) \leq p(|x|)$ und $DTIME_T(x) \leq 2^{p(|x|)}$ wobei $p$ ein Polynom ist.
    Außerdem habe $T$ zu jeder Eingabe $x$ genau eine Startkonfiguration $a_{INI}$ und eine akzeptierende Endkonfiguration $a_{ACC}$.
    sodass $x \in L(T) \Leftrightarrow \exists
    a_1, a_2 \dots a_{2^{p(|x|)}}$ mit $a_1 = a_{INI}, a_{2^{p(|x|)}} = a_{ACC}$
    $a_i \rightarrow_T a_{i+1}$ wobei $\rightarrow_T$ ein Schritt der Auswertung durch T ist.
    \\
    $REACH(a, a', k) := a' \text{ ist in } 2^k \text{ Schritten von } a \text{ aus erreichbar. }$
    \\
    $x \in L \Leftrightarrow REACH(a_{INI}, a_{ACC}, p(|x|))$
    \\
    $REACH(a_{INI}, a', 0) \Leftrightarrow a \rightarrow_T a'$
    \\
    $REACH(a_{INI}, a', k+1) \Leftrightarrow \exists \check{a} . REACH(a, \check{a}, k) \land REACH(\check{a}, a', k)$

    Kodiere Konfiguration $a$ durch $p(|x|)$ viele boolesche Variablen. $a \rightarrow_T a'$ durch quantorenfreie boolesche Formel.
    \\
    Dies, zusammen mit Abwicklung der Rekursion, liefert eine $QBF_1$-Formel (nur Existenzquantoren), also wäre $PSPACE \subseteq NP$. Das ist natürlich falsch, denn die so erhaltene $QBF_1$-Formel hat die Größe $\Omega(2^{p(|x|)})$.
    \\
    Die Aufblähung findet nicht statt, wenn man folgende Rekurenz verwendet:
    \\
    $REACH(a,a') \Leftrightarrow a \rightarrow_T a'$
    \\
    $REACH(a,a') \Leftrightarrow \exists \check{a} \forall b \forall b' .
    (b = a \land b' = \check{a} \lor b = \check{a} \land b' = a') \Rightarrow REACH(b, b', k)$
    \\
    % TODO lalalala '-W' zeichen worte keine ahnung
    Die Größe von $REACH(a, a', k)$ ist $\bigO(k * p(|x|))$  lalalalala $\bigO(p(|x|)^2)$


\end{beweis}


Die Charakterisierung von $PSPACE$ durch QBF liefert einen direkten Zusammenhang zu Gewinnstrategien in endlichen 2-Personen-Spielen.
Die Existenz einer Gewinnstrategie kann in offensichtlicher Weise als $QBF$-Formeln können selbst als 2-Personen-Spiel verstanden werden.
\\
Man kann ein entsprechendes Maschinenmodell definieren, die \definiere{alternierenden Turingmaschinen}.






\begin{beispiel}


    Gegeben ein Graph $G = (V,E)$.
    \\
    Knoten entsprechen beliebiger Belegung von boolesche Variablen. Kanten durch boolesche Formeln repräsentiert. Die Nachbarknoten eines Knoten können aufgezählt werden. $s, t \in V$ vorgegeben.

    Es werden abwechselnd Marken auf den Graphen gesetzt. Spieler 1 hat weiße Marken, Spieler 2 hat schwarze Marken. Ein Spieler hat gewonnen, wenn es einen Pfad seiner Farbe von $s$ nach $t$ gibt.

    Gefragt ist, ob Spieler 1 gewinnen kann. Man zeige, dass dieses Problem PSPACE-vollständig ist.

\end{beispiel}














\datum{14.12.15}


\section{Noch zwei PSPACE-vollständige Probleme}


\begin{definition}

    \definiere{GENERALIZED GEOGRAPHY} (GGEO)

    Gegeben: Gerichteter Graph $G = (V, E)$ und Startknoten $s \in V$.

    Folgendes Zwei-Parteien-Spiel wird auf $G$ gespielt: Die Parteien ziehen abwechselnd eine Marke entlang der Kanten des Graphen beginnend bei $s$. Einmal besuchte Knoten dürfen nicht wieder besucht werden. Wer nicht mehr ziehen kann, hat verloren.

    Gefragt: Besitzt die anziehende Partei eine Gewinnstrategie?

\end{definition}


\begin{satz}

    GGEO ist PSPACE-vollständig.

\end{satz}

\begin{beweis}

    \begin{itemize}

        \item ``$\in PSPACE$'':

        Wir betrachten die Funktion
        \\
        $ WIN(v \in V, B \subseteq V) =
        \begin{cases}
        true         & \text{ , falls GGEO kann von v aus gewonnen werden auf  } (V \setminus B, E)     \\
        false         &  \text{ , sonst }    \\
        \end{cases}
        $

        Es ist $WIN(v \in V, B \subseteq V) =
        \\\text{ if } v \in B \lor \forall w. (v,w) \in E \Rightarrow w \in B
        \\\text{ then } false
        \\\text{ else } \exists w . (v,w) \in E \land w \notin B \land \forall w' . (w,w') \in E \land w' \notin B \Rightarrow WIN(w', B \cup \{ v,w \})$

        $WIN$ kann rekursiv (mit Stack\footnote{Tiefe beschränkt durch Anzahl der Knoten} wie bei Savitch) in $PSPACE$ ausgewertet werden.


        % TODO:
        % ein paar mehr footnotes benutzen im ganzen tex, wo ich hässlich geklammert hab


        \item ``PSPACE''-hart:

        Wir geben eine Reduktion von QBFSAT auf GGEO.

        Sei eine Instanz $\phi$ von QBFSAT gegeben. O.\,B.\,d.\,A. habe $\phi$ folgende Form:
        \\
         $\exists x_1 \forall x_2 \exists x_3 \forall \dots \exists x_n . \Phi(x_1 \dots x_n)$ (KNF).


    \end{itemize}

\end{beweis}





\begin{definition}


    \definiere{Universalität von NEA} (NEA-UNIV)

    Gegeben: nichtdeterministischer endlicher Automat $A = (\Sigma, Q, \delta, q_0, F)$

    Gefragt: $L(A) = \Sigma^ast$

\end{definition}


\textbf{Bemerkung:}\\
Zu entscheiden, ob $L(A) = \emptyset$ ist in $NLOGSPACE \subseteq \ComplexityClassP$, denn es ist äquivalent zu der Frage, ob $E$ von $q_0$ aus erreichbar ist im Graphen $(Q,K)$ wobei
$K = \{ (q, q') \quad | \quad \exists a \in Sigma : (q, a, q') \in \delta \}$

Sei $B$ der zu $A$ äquivalente deterministische endliche Automat\footnote{Das kennen wir ja, mit der Teilmengenkonstruktion...} und $\overline{B}$ dessen Komplement. Es ist $L(A) = \Sigma^\ast \Longleftrightarrow L(\overline{B}) = \emptyset$.
\\
Wenn man den ``Potenzautomaten'' $B$ beziehungsweise sein Komplement $\overline{B}$ nicht explizit, sondern ``on demand'' aufbaut, kann die Suche in $\overline{B}$ in $PSPACE$ erfolgen.




\begin{satz}

    NEA-UNIV ist PSPACE-vollständig.

\end{satz}

\begin{beweis}

    \begin{itemize}

        \item ``$\in PSPACE$'':

        Bereits gezeigt.


        \item ``PSPACE''-hart:

        Sei eine normalisierte (im üblichen Sinne) deterministische Turingmaschine $T$ mit polynomiellen Platzverbrauch und eine Eingabe $x$ vorgelegt.
        \\
        Alle globalen Konfigurationen durch Strings der Länge $N = p(|x|)$ kodiert in vernünftiger Weise. Genau eine akzeptierende Endkonfiguration $q_{ACC}$.

        Berechnungen von $T$ auf $x$ lassen sich also durch Wörter der Form $w = a_0 a_1 a_2 \dots a_n$ repräsentieren, wobei $a_0 = a_{INI}$ (Startkonfiguration zu Eingabe $x$).

        % TODO    T
        $a_i \rightarrow a_{i+1} $ für $i = 0 \dots n-1$
        \\
        insbesondere $|a_i| = N$

        $a_n$ Endkonfiguration ($q_{ACC}$ oder nicht).

        $x \in L(T) \Leftrightarrow \exists w . w \text{ hat diese Form und } a_n = q_{ACC}$
        \\d.\,h.
        $x \in L(T) \Leftrightarrow \forall w . w \text{ ist keine Berechnung beginnend bei } x \lor w \text{ hört mit } q_{ACC} \text{ auf. }$

        Die Eigenschaften
        \\
        $U_x \Longleftrightarrow w \text{ ist keine Berechnung beginnend bei } x $
        \\
        $V_x \Longleftrightarrow w \text{ hört nicht mit } x \text{ auf. }$
        \\
        können durch nichtdeterministische endliche Automaten geprüft werden, die aus $x$ in polynomieller Zeit (sogar FL) berechnet werden können.

        Skizze der Konstruktion dieser Automaten:
        \begin{itemize}

            \item Für $U_x$:

            Prüfe, dass die ersten $N$ Symbole der Eingabe der Konfiguration $a_{INI}$ zu $x$ entsprechen. Dies kann mit $N$ Zuständen fest verdrahtet werden.
            \\
            Falls nicht, so wird sofort akzeptiert.
            \\
            Ansonsten muss der Automat für $U_x$ nichtdeterministisch einen Fehler in $w$ raten.
            \begin{itemize}
                \item Letzte $N$ Symbole sind keine Haltkonfiguration.
                \item Eingabe hat die Form $u w_1 u w_2 v w_3$ wobei $|u w_2| = N$ und $|u| = |v| = 7$ und $u, v$ entsprechen einander in aufeinanderfolgenden Konfigurationen.
                $v$ ist nicht entsprechender Teil der Folgekonfigurationen.
            \end{itemize}

            % z.B. lalalala
            % TODO weiß eh nicht wo das zugehört und was das soll und überhaupt
            % z.B. Kopf nicht bei $u, v$ und doch $u \neq v$
            % oder Kopf bei $u$ und Kopf an falsher..


            Nach Konstruktion ist also ein Automat $A_x$ entstanden mit $L(A_x) = U_x v V_x$ also $L(A_x) = \Sigma^\ast \Leftrightarrow x \in L(T)$



            \item Für $V_x$:

            So ähnlich.


        \end{itemize}

    \end{itemize}

\end{beweis}









\datum{17.12.15}


\section{Jumping Automata on Graphs}

\begin{definition}

    Gegeben ein Alphabet $\Sigma$.

    Eine \definiere{Zeigerstruktur} über $\Sigma$ ist ein Paar $(V, E)$ wobei
    \begin{itemize}
        \item $V$ eine endliche Menge von Knoten und
        \item $E \subseteq V \times \Sigma \rightarrow V$
                \\
                Notation: $v.l = E(v,l) \text{ für } v \in V \text{ und } l \in \Sigma$
    \end{itemize}

    Vorstellung: Knoten sind Objekte. Alphabetsymbole sind Feldnamen/Pointer.


\end{definition}

\begin{beispiel}

    Ein regulärer ungerichteter Graph vom Grad $d$:
    \begin{itemize}
        \item Jeder Knoten hat genau $d$ Nachbarn (``regulär'').
        \item Die Nachbarn eines Knotens sind linear angeordnet (nummeriert von $1$ bis $d$).
    \end{itemize}

    % TODO: tikz einfach so ein Gitter

    Als Zeigerstruktur: $\Sigma \{ 1 \dots d \} . E(v,i) = \text{ i-ter Nachbar von } v$.

\end{beispiel}

\begin{beispiel}

    Gerichtete reguläre Graphen vom Grad $d$ kann man ebenso als Zeigerstruktur über $\Sigma = \{ 1 \dots d \}$ , oder besser, falls Kanten auch in umgekehrter Richtung navigiert werden können, über $\Sigma = \{ 1 \dots d \} \cup \{ 1' \dots d' \} $ darstellen.

\end{beispiel}

\begin{beispiel}

    Nicht-reguläre Graphen (Knoten haben beliebig viele Nachbarn) können durch Adjazenzlisten repräsentiert werden, z.\,B. zirkulär $\Sigma = \{ head, next, elem \}$.

    Dabei hab ein Knoten ein Pointer mehr als Nachbarn: Knoten $a$ zeigt mit $head$ auf $a_1$, $a_1$ mit $next$ auf $a_2$, $a_2$ mit $next$ auf $a_1$. $a_1$ zeigt mit $elem$ auf $b$ und $a_2$ mit $elem$ auf $b$ usw.

\end{beispiel}

\begin{beispiel}

    Sogar Graphen ohne Ordnung auf den Nachbarn können so repräsentiert werden.

    $(V, E), E \subseteq V \times V
    \\
    \leadsto V \times E, \mathcal{E}
    \\
    \Sigma = \{ s, t \}
    \\
    \mathcal{E}: (v, v').s = v
    \\ \quad  (v, u').t = v'
    \\ \quad  v.s = v'
    \\ \quad  v.t = v
    $

\end{beispiel}

\begin{beispiel}

    Gegeben: Endliche Gruppe $G$ mit Erzeugern $g_1 \dots g_d$

    $\leadsto$ Zeigerstruktur $\Sigma = \{ g_1 \dots g_d, g_1^{-1} ,\dots g_d^{-1}$,
    $V = G$,
    $v.l = v * l$ wobei $*$ die Gruppenmultiplikation ist.

\end{beispiel}




\begin{definition}

    Ein \definiere{Jumping Automata on Graphs} (JAG) ist ein Quintupel $(\Sigma, Q, q_0, \delta, P)$ wobei
    \begin{itemize}
        \item $\Sigma$ Alphabet
        \item $Q$ Zustände
        \item $q_0 \in Q$ Startzustand
        \item $P$ Pebbles
        \item $\delta$ Menge von Quadrupeln der Form $(q, S, q', m)$
                mit $q, q' \in Q$
                und $S$ Äquivalenzrelation auf $P$, $m: P \rightarrow P + \Sigma$:
                \\
                Falls $m(p) = p' \in P$ so muss $p$ auf die Position von $p'$ gesetzt werden.
                \\
                Falls $m(p) = l$ so muss $p$ auf $v.l$ gesetzt werden, wenn $p$ auf $v$ liegt.
    \end{itemize}

    Eine Konfiguration eines JAG auf einer Zeigerstruktur $(V, E)$ über $\Sigma$ ist ein Paar $C = (q, M)$ wobei $q \in Q, M: P \rightarrow V$.
    Die Ein-Schritt-Relation $C \Rightarrow_A C' \Longleftrightarrow   C = (q, M), C' = (q', M'), \exists (q, S, q', m) \in \delta .
    (p, p') \in S \Leftrightarrow M(p) = M(p')
    $
    Falls $m(p) = p' \in P$ dann $M'(p) = M(p')$\\
    Falls $m(p) = l$ dann $M'(p) = M(p).l$

    $A$ deterministisch, falls zu jedem $(q, S)$ genau ein $(g', m)$ mit $(q, S, q', m) \in \delta$ existiert. In diesem Fall gibt es zu jedem $C = C_0$ eine eindeutige Folge $C_0 \rightarrow C_1 \rightarrow C_2 \dots$

\end{definition}


\begin{beispiel}

    $\Sigma = \{ S, N, O, W \}$ Himmelsrichtungen

    Automat soll Pebble $b$ entlang der ersten ``freien'' Kante bewegen.
    (versperrt $v.X = v, X \in \{ S, N, O, W \}$)

    Anfang bei Pebble $s$, Stehenbleiben bei Pebble $t$.
    \\
    $s$ und $t$ werden nicht bewegt.

\end{beispiel}



\begin{satz}

    JAG-Berechnungen können durch $LOGSPACE$-Turingmaschinen simuliert werden.

\end{satz}



\begin{definition}

    Ein \definiere{deterministischer JAG} besucht einen Knoten $v$ von Knoten $s$ aus, wenn in der Berechnungsfolge beginnend bei $C_0 = (q_0, M_0), M_0(p) = s$ der Knoten $v$ irgendwann belegt ist, d.\,h. existiert $i$ sodass $C_i = (q_i, M_i), M_i(p) = u$ für ein $p \in P$

\end{definition}

\begin{satz}

    \definiere{Satz von Cook Rackoff}

    Sei $A = (\Sigma, Q, q_0, \delta, P)$ (deterministischer JAG)
    und $V = (\mathcal{Z}_m)^d$

    $\Sigma = \{ e_1 \dots e_d \} \cup \{ e_1^{-1}, e_d^{-1} \}$
    \\
    $e_i = (0 \dots 0, 1, 0 \dots 0)$ ($d$ Stück, die $1$ an Position $i$)
    \\
    $e_i^{-1} = (0 \dots 0, -1, 0 \dots 0)$ ($d$ Stück, die $1$ an Position $i$)

    Ausgehend von beliebigem $s \in \mathcal{Z}_m^d$ kann $A$ höchstens $(m  . |Q|)^{c^{|P|}}$ viele Knoten besuchen, wobei $c > 0$ eine Konstante (unabhängig von $A, m.d$) ist, durch die man das einfacher abschätzen kann.

\end{satz}

Falls $m \geq |Q|^{c^P}$
\\
$(m  . |Q|)^{c^{|P|}} \leq m^{c^{|P|}+1}$
\\
Wenn zusätzlich $d > c^{|P|} + 1$
\\
$(m  . |Q|)^{c^{|P|}} < m^d = |\mathcal{Z}_m^d|$
\\
Kein fester JAG kann alle Knoten in $\mathcal{Z}_m^d$ besuchen.

Besonderheit: $d$ ist in dem Automaten fest eingebaut. Man kann aber durch Verwendung von Adjazenzlisten auf feste Alphabetgröße reduzieren.



\begin{lemma}

    Sei $\alpha$ eine Folge von Moves $\alpha = m_1, m_2 \dots m_t$ mit $m_i: P \rightarrow P + \Sigma$

    % Falls $C$ eine Konfiguration eines JAG auf
    % (hat er schlecht formuliert hahahaha)

    Sei $M: P \rightarrow (\mathcal{Z}_m)^d$ eine Belegung.

    Wir schreiben $M' = \alpha(M)$ für die Belegung, die aus $M$ durch Abarbeiten von $\alpha$ entsteht.

    Falls $(M_i)_i$ eine Folge von Belegungen
    $M_0 \rightarrow_\alpha M_1 \rightarrow_\alpha M_2 \rightarrow_\alpha \dots \rightarrow_\alpha M_{i+1} = \alpha(M_i)$
    dann existiert $k \leq |P|, n \leq |P|! * m $ sodass $M_{k+ni} = M_k$ für alle $i \geq 0$.

    Es wiederholt sich also irgendwann nur noch oder so.


    Grund: Falls $z \in (\mathcal{Z}_m)^d$, dann ist $z^n = z z \dots z = 1$.

    Falls $\alpha$ keine Pebble-Sprünge enthält, kann man deshalb $k = 0, n = m$ wählen.

\end{lemma}


% chapter platzkomplexitaet (end)