%&LaTeX
\documentclass{article}
\usepackage{amsmath,amssymb,amsfonts}
\setlength{\textwidth}{18cm}
\setlength{\textheight}{23cm}
\hoffset-3.5cm
\begin{document}
\Large
\begin{center}
Die Bedeutung von \textsc{Reachability}
\end{center}
\begin{itemize}
    \item
    Generell:
    \begin{itemize}
	\item
        Zur L\"osung von \textsc{Reachability}-Problemen gibt es
        effiziente Algorithmen
        \item
        Anwendung auf die Konfigurationsgraphen von NDTM-Berechnungen
    \end{itemize}
\end{itemize}

\bigskip

\begin{itemize}
    \item
    \textsc{Reachability} und \textbf{NSPACE} vs. \textbf{TIME}
    \begin{itemize}
	\item
	\textsc{Reachability} $\in \mathbf{TIME}(n^3)$: DFS 
        \hfill (depth-first search)
	\item
	Folgerung:
	\[
	\mathbf{NSPACE}(r(n)) \subseteq \mathbf{TIME}(c^{\log n + r(n)})
	\]
    \end{itemize}
    
    \bigskip
    
    \item
    \textsc{Reachability} und \textbf{NSPACE} vs. \textbf{SPACE}
    \begin{itemize}
	\item
	\textsc{Reachability} $\in \mathbf{SPACE}(\log^2 n)$
	\hfill(Savitch, 1970)
	\item
	Folgerung:
	\[
	r(n) = \Omega(\log n) \Rightarrow 
	\mathbf{NSPACE}(r(n)) \subseteq \mathbf{SPACE}(r^2(n))
	\]
	\item
	Folgerung:
	\[
	\mathbf{PSPACE} = \mathbf{NPSPACE}
	\]
    \end{itemize}
    
    \bigskip
    
    \item
    \textsc{Reachability} und \textbf{NSPACE} vs. \textbf{co-NSPACE}
    \begin{itemize}
	\item
	Ist $G=(V,E)$ eine gerichteter Graph mit $n$ Knoten und
	$v \in V$, so kann man die Anzahl der von $v$ aus erreichbaren
	Knoten in $\mathcal{O}(\log n)$-\textbf{SPACE} berechnen
	\hfill (Immerman-Szelepsc\'enyi, 1988)
	\item
	Folgerung:
	\[
	r(n) = \Omega(\log n)
	\Rightarrow
	\mathbf{NSPACE}(r(n)) = \hbox{\textbf{co-NSPACE}}(r(n))
	\]
	\item
	Spezialfall: $r(n) = n$ (linear bounded NDTM):\\
	Die Stufe $\mathcal{L}_{1}$ der Chomsky-Hierarchie (kontext-sensitive 
	Sprachen) ist unter Komplementierung abgeschlossen!
    \end{itemize}
\end{itemize}

\pagebreak

\begin{center}
Konfigurationsgraph
\end{center}
$\mathcal{M}$ sei $k$ Band-(N)DTM mit 
\begin{itemize}
\item[--] Zustandsmenge $Q$
\item[--] input-Alphabet $\Sigma$
\item[--] Bandalphabet $\Gamma$, Blank-Symbol $\beta$
\item[--] Ressourcenbeschr\"ankung $r(n)$ f\"ur Band bei input $w \in \Sigma^n$
\end{itemize}
Anzahl der m\"oglichen Konfigurationen bei Bandverbrauch $r(n)$:
\[
\sharp Q \cdot
(\sharp \Gamma +1)^{k \cdot r(n)} \cdot
n \cdot r(n)^k
= \mathcal{O}(c^{\log n + r(n)})
\]
Folgerung: 
\begin{quote}
der Konfigurationsgraph $G_{\mathcal{M},w}$
der $\mathcal{M}$-Konfigurationen, die von der
Startkonfiguration mit input $w \in \Sigma^n$ aus erreichbar sind,
hat $N = \mathcal{O}(c^{log(n) + r(n)})$ Knoten.
\end{quote}
Wichtige Bemerkung f\"ur die Anwendungen:
\begin{quote}
Der Konfigurationsgraph $G_{\mathcal{M},w}$ wird \textit{nie
explizit erzeugt}, z.B. in Form einer Adjazenzmatrix.
In den Algorithmen ist es lediglich erforderlich,
Nachbarschaftsbeziehungen in $G_{\mathcal{M},w}$, d.h.
$\kappa \vdash_{\mathcal{M}} \kappa'$ f\"ur
Konfigurationspaare $(\kappa,\kappa')$, zu \"uberpr\"ufen.
Das geschieht $\textit{on demand}$ anhand einer Codierung
von $\mathcal{M}$, d.h. der Relation $\delta$.
\end{quote}

\pagebreak

\begin{itemize}
\item
Beweis von 
\[
\mathbf{NSPACE}(r(n)) \subseteq \mathbf{TIME}(c^{\log n + r(n)})
\]
\begin{itemize}
\item[--]
$L \in \mathbf{NSPACE}(r(n))$
\item[--]
$\mathcal{M}$ $k$-Band NDTM f\"ur $L$ mit Bandbeschr\"ankung $r(n)$
\item[--]
f\"ur $w \in \Sigma^n$ hat Konfigurationsgraph $G_{\mathcal{M},w}$
$N = \mathcal{O}(c^{\log n + r(n)})$ Zust\"ande und kann
von DTM f\"ur DFS mit Zeitaufwand $\mathcal{O}(N^3)$
durchsucht werden.
\item
Folgerung: $L \in \mathbf{TIME}(d^{\log n + r(n)})$
\end{itemize}

\bigskip
\bigskip

\item
Beweis von
\[
r(n) \in \Omega(\log n) \Rightarrow 
\mathbf{NSPACE}(r(n)) \subseteq \mathbf{SPACE}(r^2(n))
\]
\begin{itemize}
\item[--]
$L \in \mathbf{NSPACE}(r(n))$
\item[--]
$\mathcal{M}$ $k$-Band NDTM f\"ur $L$ mit Bandbeschr\"ankung $r(n)$
\item[--]
f\"ur $w \in \Sigma^n$ hat Konfigurationsgraph $G_{\mathcal{M},w}$
$N = \mathcal{O}(c^{\log n + r(n)}) = \mathcal{O}(c^{r(n)})$ 
(wegen $r(n) \in \Omega(\log n)$)
Zust\"ande und kann
von DTM mittels Verfahren von Savitch
mit Platzaufwand $\mathcal{O}(\log^2 N)$
durchsucht werden.
\item
Folgerung: $L \in \mathbf{SPACE}(r(n)^2)$
\end{itemize}

\pagebreak

\item
Beweis von 
\[
r(n) = \Omega(\log n)
\Rightarrow
\mathbf{NSPACE}(r(n)) = \hbox{\textbf{co-NSPACE}}(r(n))
\]
\begin{itemize}
\item[--]
$L \in \mathbf{NSPACE}(r(n))$
\item[--]
$\mathcal{M}$ $k$-Band NDTM f\"ur $L$ mit Bandbeschr\"ankung $r(n)$
\item[--]
Entwurf einer NDTM $\overline{\mathcal{M}}$ f\"ur 
$\overline{L} = \Sigma^* \setminus L$ mit Bandbeschr\"ankung $r(n)$
\begin{itemize}
\item
bei input $w \in \Sigma^*$ exekutiert $\overline{\mathcal{M}}$ den
Algorithmus \textsc{counting-reachability} auf dem
Konfigurationsgraphen $G_{\mathcal{M},w}$
\item
wird dabei akzeptierende Halt-Konfiguration von $\mathcal{M}$
entdeckt, so wird $w$ zur\"uckgewiesen (da $w \in L$ festgestellt
wurde)
\item
\textsc{counting-reachability} kann dar\"uber Auskunft geben, wann ganz
$G_{\mathcal{M},w}$ durchsucht worden ist:
wenn dabei keine akzeptierende\\
 Halt-Konfiguration angetroffen wurde,
gibt es keine akzeptierende Berechnung von
$\mathcal{M}$ auf input $w$: $w$ wird von $\overline{\mathcal{M}}$
akzeptiert.

\end{itemize}

\item
Absch\"atzung des Bandbedarfs von $\overline{\mathcal{M}}$:
\begin{itemize}
\item
Simulation der Arbeitsweise von $\mathcal{M}$ auf input $w$:
$\mathcal{O}(r(n)$
\item
Ausf\"uhrung von \textsc{counting-reachability}:
$\mathcal{O}(\log n + r(n))$\\
da $G_{\mathcal{M},w}$ $N = \mathcal{O}(c^{\log n + r(n)})$
Knoten hat und \textsc{counting-reachability}
den Bandbedarf $\mathcal{O}(\log N)$
\item
wegen $r(n) = \Omega(\log n)$ ist der Gesamtbedarf $\mathcal{O}(r(n))$
\end{itemize}
\item
Folgerung: $L \in \hbox{\textbf{co-NSPACE}}(r(n))$
\end{itemize}
\end{itemize}
\end{document}