\documentclass[12pt]{article}
\usepackage{A4}
\sloppypar
\begin{document}
\Large
\begin{center}
Weitere P-vollst\"andige Probleme
\end{center}
Neben dem ``generischen'' P-vollst\"andigen Problen
\textsc{Ciruit Value} gibt es eine grosse Anzahl weiterer
P-vollst\"andiger Probleme von praktischer Bedeutung,
auch wenn die Literatur dazu nicht ganz so umfangreich ist
wie f\"ur die NP-Vollst\"andigkeit. In vielen F\"allen handelt
es sich sich um graphentheoretische Such- und Traversierungs-Probleme,
Probleme mit Ableitungen (Deduktionen), oder auch Probleme
vom Typ ``pattern matching''.  Die heuristische Bedeutung der 
P-Vollst\"andigkeit liegt darin, dass solche Probleme zwar in
polynomialer Zeit entscheidbar sind, aber vermutlich nicht
mit effizienten \textit{parallelen} Algorithmen: jeder
effiziente parallele Algorithmus f\"ur ein einziges
P-vollst\"andiges Problem h\"atte einen 
f\"ur jedes sequentiell effizient l\"osbare Problem zur Folge.

\begin{itemize}
\item[--]
\textsc{DTM Acceptance} (schon erw\"ahnt)
\item[--]
\textsc{Linear Inequalities} (schon erw\"ahnt)\\
zu beachten: die Tatsache, dass \textsc{Linear Inequalities}
hart f\"ur \textbf{P} (unter \texttt{log-space}-Reduktionen)
ist, ist einfach einzusehen
(Reduktion von \textsc{Ciruit Value}
auf \textsc{Linear Inequalities}); viel schwieriger ist der Nachweis,
dass \textsc{Linear Inequalities} selbst zu \textbf{P}
geh\"ort (Algorithmen von \textsc{Khachian} und \textsc{Karmarkar})!

\pagebreak

\item[--]
\textsc{Path System Reachability}
\begin{itemize}
\item[$\triangleright$] Instanz:\\
Eine Knotenmenge $V$, eine Startmenge $S \subseteq V$ und
ein Zielknoten $t \in V$, sowie eine Relation 
$R \subseteq V \times V \times V$
Erreichbarkeit in diesem System ist induktiv definiert:
\begin{itemize}
\item
jedes $v \in S$ ist erreichbar
\item
sind $x,y \in V$ erreichbar und gilt $(x,y,z) \in R$,
so ist auch $z$ erreichbar.
\end{itemize}
\item[$\triangleright$] Problem:\\
Ist der Zielknoten $t$ erreichbar?
\end{itemize}
\item[--]
\textsc{Unit Resolution}
\begin{itemize}
\item[$\triangleright$] Instanz:\\
Eine Menge $\{c_1,c_2,\ldots,c_m\}$ von aussagenlogischen
Klauseln.\\
Ein unit-Resolutionsschritt besteht darin, aus einer
unit-Klausel $\{x\}$ und einer Klausel 
$\{\overline{x},y_1,\ldots,y_n\}$ die Klausel
$\{y_1,\ldots,y_n\}$ herzuleiten
\item[$\triangleright$] Problem:\\
Ist die leere Klausel mittels unit-Resolution herleitbar?
\end{itemize}

\pagebreak

\item[--]
\textsc{Context-Free Emptiness}
\begin{itemize}
\item[$\triangleright$] Instanz:\\
Eine kontextfreie Grammatik $G$
\item[$\triangleright$] Problem:\\
Ist die generierte Sprache $L(G)$ leer ?
\end{itemize}
\item[--]
\textsc{Depth-First Search}
\begin{itemize}
\item[$\triangleright$] Instanz:\\
Ein (gerichteter oder ungerichteter) Graph $G = (V,E)$
mit einem Startknoten $s$ und zwei weiteren Knoten $u,v$.
\item[$\triangleright$] Problem:\\
Wird bei von $s$ ausgehender \textit{depth-first search}
der Knoten $u$ fr\"uher als der Knoten $v$ erreicht ? 
\end{itemize}
\end{itemize}

\end{document}