\documentclass[12pt]{article}
\hoffset-3cm
\setlength{\textwidth}{18cm}
\parindent0em
\sloppypar
\usepackage{amsmath,amsfonts,amssymb}
\begin{document}
\Large
\begin{center}
Komplexit\"at von Entscheidungsproblemen
\end{center}
\begin{itemize}
\item
Beispiele f\"ur Entscheidungsprobleme
\begin{itemize}
\item
\textsc{Satisfiability (SAT)} und Varianten
\begin{itemize}
\item
\textsc{Satisfiability (SAT)}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Literale $X = \{x_1, \overline{x_1}, \ldots, x_n,
\overline{x_n}\}$, \\
Klauseln $c_1,c_2, \ldots,c_m$,
wobei
$c_j \subseteq X, (1 \leq j \leq m)$.
\item[$\triangleright$]
Problem: \\
gibt (mindestens) eine Bewertung, die alle Klauseln
simultan wahr macht?\\ 
($\Leftrightarrow$ Erf\"ullbarkeit Boolescher Formeln in POSE)
\end{itemize}
\item
\textsc{3-SAT}: wie SAT, aber mit $|c_j|\leq 3~(1 \leq j\leq m)$
\item
\textsc{2-SAT}: wie SAT, aber mit $|c_j|\leq 2~(1 \leq j\leq m)$
\item
\textsc{Unsatisfiability}: Instanzen wie SAT, aber
\begin{itemize}
\item[$\triangleright$]
Problem:\\
Gibt es \textit{keine} Bewertung, die alle Klauseln
simultan wahr macht?
\end{itemize}
\item
\textsc{Tautology (TAUT)}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Boolesche Formel (Funktion) in SOPE
\item[$\triangleright$]
Problem:\\
Hat die Formel unter jeder Bewertung den Wert 1?
\end {itemize}

\pagebreak

\item
\textsc{Circuit-SAT}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Schaltkreis mit input f\"ur $x_1,\ldots,x_n$ und
ausgezeichnetem output-Knoten
\item[$\triangleright$]
Problem:\\
Gibt eine input-Belegung, die dem output-Knoten
den Wert 1 gibt?
\end{itemize}
\item
\textsc{Circuit Value}: 
\begin{itemize}
\item[$\triangleright$]
Instanz :\\
Schaltkreis mit input f\"ur $x_1,\ldots,x_n$ und
ausgezeichnetem output-Knoten und Belegung der
input-Knoten mit Booleschen Werten
\item[$\triangleright$]
Problem:\\
Hat der output-Knoten den Wert 1 ?
\end{itemize}
\end{itemize}

\pagebreak

\item
Probleme mit Graphen
\begin{itemize}
\item
\textsc{Graph Reachability}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Graph $G = (V,E)$ und zwei Knoten $u,v \in V$
\item[$\triangleright$]
Problem:\\
Gibt es in $G$ einen Pfad von $u$ nach $v$ ?
\end{itemize}

\item
\textsc{Connectedness}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Graph $G = (V,E)$
\item[$\triangleright$]
Problem:\\
Gibt es f\"ur je zwei Konten $u,v \in V$
einen Pfad von $u$ nach $v$ in $G$?
\end{itemize}

\item
\textsc{Eulerian Circuit}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Ein Graph $G = (V,E)$
\item[$\triangleright$]
Problem:\\
Hat $G$ einen (geschlossenen) Pfad, der jede \textit{Kante}
genau einmal benutzt?
\end{itemize}

\item
\textsc{Hamiltonian Circuit}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Ein Graph $G = (V,E)$
\item[$\triangleright$]
Problem:\\
Hat $G$ einen (geschlossenen) Pfad, der jeden \textit{Knoten}
genau einmal besucht?
\end{itemize}

\pagebreak

\item
\textsc{Graph-k-Colorability}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Graph $G = (V,E)$ und nat\"urliche Zahl $k \in \mathbb{N}$
\item[$\triangleright$]
Problem:\\
Gibt es eine Funktion $f:V \rightarrow \{1,2,\ldots,k\}$,
so dass f\"ur alle Kanten $(u,v) \in E$ gilt: $f(u) \neq f(v)$ ?

\end{itemize}

\bigskip

\item
\textsc{3-Colorability}: wie \textsc{Graph-k-Color.},
aber mit $k=3$

\bigskip

\item
\textsc{2-Colorability}: wie \textsc{Graph-2-Color.},
aber mit $k=2$

\bigskip

\item
\textsc{Planar-k-Colorability}: wie \textsc{Graph-k-Color.},
aber f\"ur planare Graphen


\pagebreak

\item
\textsc{k-Clique, k-Independent Set}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Ein Graph $G = (V,E)$ und eine Zahl $k \in \mathbb{N}$
\item[$\triangleright$]
Problem:\\
Gibt es eine $k$-elementige Teilmenge $K$ von $V$ derart,
dass alle Kanten $(u,v) \in K \times K$ zu $E$ geh\"oren,
bzw. nicht zu $E$ geh\"oren?
\end{itemize}

\bigskip

\item
\textsc{Graph Isomorphism}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Zwei Graphen $G = (V,E)$ und $G' = (V',E')$  
\item[$\triangleright$]
Problem:\\
gibt
es eine bijektive Abbildung $f:V \rightarrow V'$ mit der
Eigenschaft: $(u,v) \in E \leftrightarrow (f(u),f(v))\in E'$?

\end{itemize}

\end{itemize}

\pagebreak

\item
Varianten von Optimierungs- und Scheduling-Problemen
\begin{itemize}
\item
\textsc{Travelling Salesperson Problem (TSP)}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Graph $G=(V,E)$\\
Bewertungsfunktion 
$ w \,:\;E \rightarrow \mathbb{N}$\\
ganze Zahl $k$
\item[$\triangleright$]
Problem:\\
Gibt es eine ``Rundreise'' durch $G$, bei der jeder Knoten
einmal besucht wird und die Gesamtkosten 
(= Summe der Gewichte der ben\"utzten Kanten)
$\leq k$ bleiben?
\end{itemize}

\bigskip

\item
\textsc{Spanning Tree (ST), Ger\"ust}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Graph $G=(V,E)$\\
Bewertungsfunktion 
$ w \,:\;E \rightarrow \mathbb{N}$\\
ganze Zahl $k$
\item[$\triangleright$]
Problem:\\
Gibt es ein ``Ger\"ust'' von $G$, d.h. einen Untergraphen, der
ein Baum ist und der jeden Knoten enth\"alt,
dessen Gesamtkosten 
(= Summe der Gewichte der ben\"utzten Kanten)
$\leq k$ sind?
\end{itemize}

\pagebreak


\item
\textsc{Integer Programming (IP)}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
System von linearen Ungleichungen mit ganzzahligen\\
Koeffizienten
\item[$\triangleright$]
Problem:\\
Hat dieses System eine ganzzahlige L\"osung?
\item[$\bullet$] Bemerkung: viele bekannte Probleme
wie \textsc{Knapsack},\\ \textsc{Bin Packing},
\textsc{Subset Sum}, \ldots, sind Spezialisierungen
von IP.
\end{itemize}

\item
\textsc{Linear Inequalities (LP)}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Ganzzahlige $m \times n$-Matrix $\mathbf{A}$ und Vektor $\mathbf{b}$
\item[$\triangleright$]
Problem:\\
Gibt es eine rationale L\"osung $\mathbf{x}$ der Ungleichung
$\mathbf{A} \cdot \mathbf{x} \geq \mathbf{b}$ 
(komponentenweise), wobei $\mathbf{x} \geq 0$ sein soll,
aber $\mathbf{x} \neq \mathbf{0}$?
\end{itemize}

\pagebreak

\item
\textsc{Task Sequencing}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
$r$ Tasks mit\\
Ausf\"uhrungsdauern $t_1,\ldots,t_r$,\\
deadlines $d_1, \ldots,d_r$,\\
Strafen $p_1,\ldots,p_r$,\\ 
sowie $k \geq 1$.
\item[$\triangleright$]
Problem:\\
Gibt es eine Permutation $\pi$ von $\{1,2,\ldots,r\}$ mit
\[
\sum_{j=1}^r 
\left[
\,\text{\bf if}\,
\,t_{\pi(1)} + t_{\pi(2)} + \ldots +t_{\pi(j)} > d_{\pi(j)}
\,\text{\bf then} \,
p_{\pi(j)}
\,\text{\bf else}\, 0 
\right]
\leq k
\]
\end{itemize}

\end{itemize}

\pagebreak

\item{Ein Problem \"uber DTMs}
\begin{itemize}
\item
\textsc{DTM Acceptance}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Beschreibung einer DTM $\mathcal{M}$, 
input-Wortes $w$ und
nat\"urlichen Zahl $n$ in un\"arer Codierung
\item[$\triangleright$]
Problem:\\
H\"alt $\mathcal{M}$ bei input $w$ in nicht mehr als $n$ Schritten?
\end{itemize}
\end{itemize}


\bigskip

\item{Ein arithmetisches Problem}
\begin{itemize}
\item
\textsc{Primality (Primes)}
\begin{itemize}
\item[$\triangleright$]
Instanz:\\
Nat\"urliche Zahl $n$ in Basis-$b$-Darstellung ($b \geq 2$)
\item[$\triangleright$]
Problem:\\
Ist $n$ eine Primzahl?
\end{itemize}

\end{itemize}
\end{itemize}

\pagebreak

\item
Sprachen und Probleme
\begin{itemize}
\item
$\Sigma$ Alphabet
\item
$I \subseteq \Sigma^*$ :
Instanzenmenge eines Problems
\item
Problem $\mathcal{P}$ gegeben durch Partition
$(I_{\text{yes}},I_{\text{no}})$ von $I$, d.h.
\[
I_{\text{yes}} \cup I_{\text{no}} = I~,~
I_{\text{yes}} \cap I_{\text{no}} = \emptyset
\]
\item
komplement\"ares Problem:
co-$\mathcal{P} = (I_{\text{no}},I_{\text{yes}})$
\item
Sprache des Problems: 
$L(\mathcal{P}) = I_{\text{yes}} \subseteq{\Sigma^*}$
\end{itemize}
Bemerkungen zur Codierung:
\begin{itemize}
\item
Die Instanzenmenge $I$ eines Problems $\mathcal{P}$
ist meist regul\"ar; es ist also leicht zu erkennen, ob ein
$w \in \Sigma^*$ eine Instanz ist oder nicht.
\item
Die Codierung eines Problem soll Instanzen nicht
unnat\"urlich gross machen, sondern nur relevante Information
in kompakter Form ent\-halten.
\item
Verschiedene Codierung eine Problems sollen sich gegenseitig
polynomial beschr\"anken.
\end{itemize}

\pagebreak

\item
Zielsetzung
\begin{itemize}
\item
Klassifikation von Problemen gem\"ass Ressourcenverbrauch
ihrer Entscheidungsverfahren
\item
Identifikation von (sequentiel/parallel) effizient
entscheid\-baren Problemen (``feasible'')
\item
Vergleich des Ressourcenverbrauchs bei verschiedenen
Berechnungs\-modellen
\item
Anforderung: Resultate sollen robust sein gegen\"uber 
vern\"unftiger Variation bei der Codierung und
bei vern\"uftiger Variation innerhalb einer Klasse
von Berechnungsmodellen
\end{itemize}

\item
Modelle
\begin{itemize}
\item
\textsc{Turing}-Maschinen: DTM, NDTM, k-Band-TM, ...
\item
sequentielle Random Access Maschinen: RAM
\item
parallele Random Access Maschinen: PRAM (EREW, CREW, ...)
\item
Schaltkreisfamilien
\end{itemize}

\pagebreak

\item
Deterministisches Rechnen (DTM)
\begin{itemize}
\item
deterministische k-Band \textsc{Turing}-Maschine
\[
\mathcal{M} = (Q,\Sigma,\Gamma,\beta,\delta,s,h)
\]
mit \"Ubergangs\underline{funktion}
\[
\delta :
Q \times \Sigma \times (\Gamma \cup \{\beta\})^k
\rightarrow
(Q \cup \{h\}) \times
(\Gamma \cup \{\beta\})^k \times
\{L,R\}^k \cup \perp
\]
\item
$\mathcal{M}$-Konfigurationen
\[
\kappa = (q;p_0,p_1,\ldots,p_k;x_0,x_1,\ldots,x_k)
\in
Q \times \mathbb{N}^{k+1} \times \Sigma^* \times
(\Gamma^*)^k
\]
\item
jede Konfiguration, die nicht Halt-Konfiguration ist,
hat genau eine Folgekonfiguration: deterministische
Berechnung
\item
Startkonfiguration bei input $w \in \Sigma^*$
\[
\kappa_0 = (s;0,0,\ldots;w,\varepsilon, \ldots,\varepsilon)
\]
Akzeptanz von $w$
durch Erreichen der akzeptierenden
Halt-Konfigu\-ration
\[
\kappa_a = (h;0,0,\ldots,0;w,1,\varepsilon, \ldots,\varepsilon)
\]
d.h.
\[
(s;0,0,\ldots;w,\varepsilon, \ldots,\varepsilon)
\vdash_{\mathcal{M}}^*
(h;0,0,\ldots,0;w,1,\varepsilon, \ldots,\varepsilon)
\]
\end{itemize}

\pagebreak

\item
Nichtdeterministisches Rechnen (NDTM)
\begin{itemize}
\item
$\delta$ ist eine \underline{Relation}
\[
\delta 
\subseteq
Q \times \Sigma \times (\Gamma \cup \{\beta\})^k
\times
(Q \cup \{h\}) \times
(\Gamma \cup \{\beta\})^k \times
\{L,R\}^k
\]
\item
Begriff der Konfiguration wie bei DTM; aber nun kann jede
$\mathcal{M}$-Konfiguration keine oder mehrere
Folgekonfigurationen haben; 
man kann sich auf die Situation beschr\"anken, dass jede Konfiguration 
$\leq 2$ Folgekonfigurationen hat
\item
Konzept des Konfigurationsgraphen von $\mathcal{M}$\\
(das ist ein DAG, falls alle Berechnungen terminieren)
\item
Akzeptanz: $w \in \Sigma^*$ wird akzeptiert, wenn es
\underline{mindestens} \underline {eine}
Berechnung von $\mathcal{M}$ gibt, die von der Startkonfiguration\\
$\kappa_0$
zu der akzeptierenden Halt-Konfiguration 
$\kappa_a$
f\"uhrt.
\item 
Anschaulich: Steuerung durch \textit{choice input},
Existenz von \textit{Zeugen} oder \textit{Zertifikaten}
\end{itemize}

\pagebreak


\item
Zeugen-Definition von $\mathcal{NP}$:
\[
A \in \mathcal{NP} \Leftrightarrow \left\{
\hbox{\begin{minipage}{11cm}
es gibt eine Sprache $B \in \mathcal{P}$ und ein Polynom
$p(n)$ mit
\[
w \in A \Leftrightarrow
\exists y \in \{0,1\}^{\leq p(|w|)}
(w,y) \in B
\]
d.h. $y$ ist Zeuge f\"ur die Zugeh\"origkeit von $w$ zu $A$
\end{minipage}}
\right.
\]

\item
Wie kann man sich Zeugen f\"ur co-$\mathcal{NP}$-Sprachen vorstellen?\\
vgl. \textsc{SAT} vs. \textsc{TAUT}
\pagebreak

\item
Ressourcenverbrauch bei DTM und NDTM
\begin{itemize}
\item
Vorsichtsmassnahme: Ressourcenfunktionen $r(n)$
m\"ussen
\textit{konstruierbar} (proper) sein, um unerw\"unschte
Effekte auszuschliessen. Die ``\"ublichen" Funktionen
(Logarithmus, Polynome, Exponentialfunktionen, etc.)
haben diese Eigenschaft, diese jetzt immer
vorausgesetzt wird.
\item
$L \in \hbox{\textsc{Time}}(r(n))$ :
es gibt eine DTM $\mathcal{M}$, die $L$ akzeptiert, wobei
$\mathcal{M}$ auf jedem input $w \in \Sigma^*$ genau
(oder $\leq$) $r(|w|)$ Takte rechnet und sich dann in einem
akzeptierenden oder nicht-akzeptierenden Halt-Zustand befindet.
\item
$L \in \hbox{\textsc{Space}}(r(n))$ :
es gibt eine DTM $\mathcal{M}$, die $L$ akzeptiert, wobei
$\mathcal{M}$ auf jedem input $w \in \Sigma^*$ genau
(oder $\leq$) $r(|w|)$ Felder der $k$ Arbeitsb\"ander
benutzt und sich dann in einem akzeptierenden oder
nicht-akzeptierenden Halt-Zustand befindet.
\item 
$\hbox{\textsc{NTime}}(r(n))$ und
$\hbox{\textsc{NSpace}}(r(n))$
werden analog mit NDTM statt DTM definiert.
\end{itemize}

\item
Wichtig: die so definierten Komplexit\"atsklassen
pr\"azisieren die Idee der {\it worst-case Komplexit\"at};\\
Algorithmen mit schlechtem worst-case Verhalten k\"onnen
im {\it average-case} durchaus effizient sein.

\pagebreak

\item
Allgemeine Beziehungen zwischen Komplexit\"atsklassen\\[3mm]
$r(n),s(n)$ seien Ressourcenfunktionen
\begin{itemize}
\item
$r(n) \leq s(n) \Rightarrow
\hbox{\textsc{Time}}(r(n)) \subseteq \hbox{\textsc{Time}}(s(n))$
\bigskip
\item
$r(n) \leq s(n) \Rightarrow
\hbox{\textsc{Space}}(r(n)) \subseteq \hbox{\textsc{Space}}(s(n))$
\bigskip
\item
$\hbox{\textsc{Time}}(r(n)) \subseteq \hbox{\textsc{NTime}}(r(n))$
\bigskip
\item
$\hbox{\textsc{Space}}(r(n)) \subseteq \hbox{\textsc{NSpace}}(r(n))$
\bigskip
\item
$\hbox{\textsc{NSpace}}(r(n)) \subseteq 
\hbox{\textsc{Time}}(k^{\log n + r(n)})$
\bigskip
\item
$\hbox{\textsc{NTime}}(r(n)) \subseteq 
\hbox{\textsc{Space}}(r(n))$
\bigskip
\item
$r(n) \geq n \Rightarrow 
\hbox{\textsc{Time}}(r(n)) \subsetneqq 
\hbox{\textsc{Time}}(r(n)\cdot \log r(n))$
\bigskip
\item
$r(n) = o(s(n)) \Rightarrow 
\hbox{\textsc{Space}}(r(n)) \subsetneqq 
\hbox{\textsc{Space}}(s(n))$
\bigskip
\item
$r(n) = \Omega(\log n) \Rightarrow
\hbox{\textsc{NSpace}}(r(n)) \subseteq 
\hbox{\textsc{Space}}(r(n)^2)$
\end{itemize}

\bigskip

Bem.: durch Wechsel des Bandalphabets kann man Ressourcenverbrauch
um konstanten Faktor modifizieren, daher 
$\hbox{\textsc{Time}}(r(n)) = \hbox{\textsc{Time}}(c \cdot r(n))$
usw.
\pagebreak

\item
wichtige Komplexit\"atsklassen
\begin{itemize}
\item
sequentielle Klassen
\begin{align*}
\mathbf{L} &= \textsc{Space}(\log n)\\
\mathbf{NL} &= \textsc{NSpace}(\log n)\\
\mathbf{L^2} &= \textsc{Space}(\log^2 n)\\[5mm]
\mathbf{P} &= \bigcup_k \textsc{Time}(n^k)\\
\mathbf{NP} &= \bigcup_k  \textsc{NTime}(n^k)\\[5mm]
\mathbf{PSPACE} &= \bigcup_k \textsc{Space}(n^k)\\
\mathbf{NPSPACE} &= \bigcup_k  \textsc{NSpace}(n^k)\\[5mm]
\mathbf{EXPTIME} &= \bigcup_k \textsc{Time}(k^n)\\
\mathbf{NEXPTIME} &=\bigcup_k  \textsc{NTime}(k^n)
\end{align*}

\item
parallele Klassen:
$\mathbf{NC^k}$ = ``uniforme'' Schaltkreise mit Gr\"osse
\textit{poly}($n$) und Tiefe $\mathcal{O}(\log^k(n))$
\[
\mathbf{NC} = \bigcup_{k \geq 1} \mathbf{NC}^k
\]
\end{itemize}

\item
Tatsachen:
\[
\mathbf{L} \subseteq
\mathbf{NL} \subseteq
\mathbf{P} \subseteq
\mathbf{NP} \subseteq
\left\{\hbox{
\begin{minipage}{3.2cm}
$\mathbf{PSPACE} \\=\\
\mathbf{NPSPACE}$
\end{minipage}}
\right\}
\subseteq
\mathbf{EXPTIME} \subseteq 
\mathbf{NEXPTIME}
\]
\[
\mathbf{P} \neq \mathbf{EXPTIME}
\]
\[
\mathbf{NL} \subseteq \mathbf{L^2}
\subseteq \mathbf{NP}
\]
\[
\mathbf{NC^1} \subseteq 
\mathbf{L} \subseteq
\mathbf{NL} \subseteq
\mathbf{NC^2}\subseteq
\mathbf{NC^k}_{\{k \geq 2\}} \subseteq 
\mathbf{NC} \subseteq
\mathbf{P}
\]

\bigskip
\item
Welche Probleme sind effizient entscheidbar/berechenbar?
\begin{itemize}
\item
sequentielle Berechnung: $\mathbf{P}$
\item
Verifikation: $\mathbf{NP}$
\item
parallele Berechnung: $\mathbf{NC}$
\item
interaktive Berechnung: $\mathbf{PSPACE}$
\end{itemize}

\item
Offene Fragen: 
\begin{itemize}
\item
Welche dieser Inklusionen sind \textit{echt}
und welche sind es nicht?
\item
Komplementierung f\"ur nichtdeterministische Klassen
\end{itemize}
\end{itemize}

\pagebreak

\begin{list}{$\bullet$}{\itemsep1cm}
\item
Literatur zum \textbf{P}-vs.-\textbf{NP}-Problem
\begin{list}{---}{\itemsep0.5cm}
\item
Die grundlegenden Arbeiten:
\begin{list}{*}{}
\item
{\sc S. Cook} :
\newline
``The complexity of theorem proving procedures'',
{\em Proc. 3rd. ACM Symposium Theory of Computing} 1971.
\newline
{\small
[Formulierung des Problems ``$\mathbf{P}$  vs. $\mathbf{NP}$'',
Nachweis der $\mathbf{NP}$-Vollst\"andigkeit von {\sc Sat}]}
\item
{\sc R. Karp} :
\newline
``Reducibility among combinatorial problems'',
\newline
in {\sc Miller/Thatcher}, {\em Complexity of Computer Computations},
Plenum Press, 1972.
\newline
{\small
[Zeigt anhand von Reduktionen die Reichhaltigkeit 
der Problemklasse $\mathbf{NPC}$]}
\item
``Vorl\"aufer'' sind Arbeiten von {\sc Cobham} (1964), {\sc
Edmonds} (1965), {\sc Levin} (1973), {\sc Yablonski} (1959).
\item
Ein ``spekulativer'' Brief von {\sc K. G\"odel} an {\sc J.v. Neumann}
(in Deutsch), 20. M\"arz 1956.
\newline
(reproduziert bei {\sc Sipser}, s.u.)
\end{list}
\newpage
\item
Die klassische Referenz
\begin{list}{*}{}
\item
{\sc M.R. Garey, D.S. Johnson} :
\newline
{\em Computers and Intractability. A Guide to the Theory
of NP-Completeness}, Freeman, 1979.
\end{list}
\item
Daneben viele Lehrb\"ucher mit sehr guten Darstellungen,
von \\
{\sc Hopcroft/Ullman} (1979) bis zu
{\sc Papadimitriou} und \\
{\sc Bovet/Crescenzi} (beide 1994).
\item
Historischer \"Uberblick und Ausblick
\begin{list}{*}{}
\item
{\sc M. Sipser} :
\newline
``The history and status of the $\mathbf{P}$  vs. $\mathbf{NP} $
question'',
\newline
{\em Proc. 24 ACM Symposium Theory of Computing}, 1992.
\item
{\sc R. Book} :
\newline
``Relativizations of the $\mathbf{P}\  ?\!= \mathbf{NP}$  and other
problems: \\
Developments in structural complexity theory'',
\newline
SIAM Review, 1994.
\end{list}
\end{list}
\end{list}
\end{document}