%&LaTeX
\documentclass[12pt]{article}
\usepackage{amsmath,amssymb,amsfonts}
\setlength{\textwidth}{18cm}
\setlength{\textheight}{23cm}
\hoffset-2cm
\parindent0em
\sloppypar
\begin{document}
\Large

\begin{center}
Reduktion, vollst\"andige Probleme
\end{center}

F\"ur Sprachen $L_1 \subseteq \Sigma_1^*, L_2 \subseteq \Sigma_2^*$:\\
\textit{(many one) Reduktion (Transformation)} von $L_1$ auf $L_2$ ist
\[
h\,:\,\Sigma_1^* \rightarrow \Sigma_2^*~~\text{mit}~~
\forall w \in \Sigma_1^*: w \in L_1 \Leftrightarrow h(w) \in L_2
\]

\bigskip
\bigskip

Ressourcenbeschr\"ankte Reduktion:\\ 
$h$ ist (auf DTM) mit
beschr\"ankten Ressourcen berechenbare Funktion

\bigskip
\bigskip

$R$ : Ressourcenbeschr\"ankung (Reduktionsklasse),\\
hier 
$R = \hbox{\texttt{log-space}}~\text{oder}~
\hbox{\texttt{poly-time} = \texttt{p}}$

\bigskip
\bigskip

Reduktion f\"ur Probleme:
\[
\mathcal{P}_1 \leq_R \mathcal{P}_2~:~
\hbox{
\begin{minipage}{10cm}
$\mathcal{P}_1$ kann auf $\mathcal{P}_2$ transformiert (reduziert)
werden mit Ressourcenbeschr\"ankung $R$
\end{minipage}
}
\]
Anschaulich: das Entscheidungsproblem f\"ur $\mathcal{P}_1$
ist nicht aufwendiger als das Entscheidungsproblem 
f\"ur $\mathcal{P}_2$  --- oder anders herum: jeder
Algorithmus zur  Entscheidung $\mathcal{P}_2$ liefert (vermittels $h$)
sogleich einen Algorithmus f\"ur $\mathcal{P}_1$, der 
(bis auf die --- hoffentlich geringen --- Kosten f\"ur $h$)
nicht aufwendiger ist.

\pagebreak

Bemerkung: log-space-beschr\"ankte Berechnungen sind
polynomial \\
zeit\-beschr\"ankt, daher 
\[
\mathcal{P}_1 \leq_{\mathtt{log-space}} \mathcal{P}_2
~\Rightarrow~
\mathcal{P}_1 \leq_{\mathtt{p}} \mathcal{P}_2
\]

\bigskip

W\"unschenswerte Eigenschaft: Transitivit\"at!
\[
\mathcal{P}_1 \leq_R \mathcal{P}_2
\wedge
\mathcal{P}_2 \leq_R \mathcal{P}_3
~\Rightarrow~
\mathcal{P}_1 \leq_R \mathcal{P}_3
\]
-- dies gilt f\"ur $R$ = \texttt{poly-time} (einfach)\\[3mm]
-- dies gilt f\"ur $R$ = \texttt{log-space} (nicht so einfach!)

\bigskip
\bigskip

Sinnvolle Forderung:\\
Vertr\"aglichkeit f\"ur Komplexit\"atsklasse
$\mathcal{C}$ und \\Reduktionsklasse $R$:
\[
\mathcal{P}_1 \leq_R \mathcal{P}_2
\wedge
\mathcal{P}_2 \in \mathcal{C} 
~\Rightarrow~
\mathcal{P}_1 \in \mathcal{C}
\]
Anschaulich: in der Transformation $h$ soll nicht wesentlich
Arbeit zur L\"osung des Entscheidungsproblems selbst geleistet werden.
Sonst k\"onnte man ja ein ``schwieriges'' Problem 
$\mathcal{P}_1$ auf ein ``leichtes'' Problem $\mathcal{P}_2$ 
reduzieren.

\pagebreak

\textit{H\"arte}:
\begin{quote}
$\mathcal{C}$ Komplexit\"atsklasse,\\
$R$ Reduktionsklasse (+ Vertr\"aglichkeit),\\
$\mathcal{Q}$ Problem\\
$\mathcal{Q}$ ist \textit{hart f\"ur $\mathcal{C}$ unter $R$-Reduktionen}:
\[
\forall \mathcal{P} \in \mathcal{C}~:~
\mathcal{P} \leq_R \mathcal{Q}
\]
\end{quote}

\bigskip

\textit{Vollst\"andigkeit}: 
\begin{quote}
$\mathcal{C}$ Komplexit\"atsklasse,\\
$R$ Reduktionsklasse (+ Vertr\"aglichkeit),\\
$\mathcal{Q}$ Problem\\
$\mathcal{Q}$ ist \textit{vollst\"andig f\"ur $\mathcal{C}$ unter $R$-Reduktionen}:
\[
\mathcal{Q} \in \mathcal{C} \wedge
\forall \mathcal{P} \in \mathcal{C}~:~
\mathcal{P} \leq_R \mathcal{Q}
\]
\end{quote}

\bigskip

Bemerkung: die \textit{Existenz} vollst\"andiger Probleme ist
keineswegs garantiert!

\pagebreak

Die wichtigsten F\"alle:
\begin{align*}
\mathcal{C} = \mathbf{P} , R = \hbox{\texttt{log-space}}
& ~:~ &\mathbf{P}\hbox{-vollst\"andige Probleme}\\
\mathcal{C} = \mathbf{NP} , R = \hbox{\texttt{poly-time}}
& ~:~ & \mathbf{NP}\hbox{-vollst\"andige Probleme}\\
\mathcal{C} = \mathbf{PSPACE} , R = \hbox{\texttt{poly-time}}
&  ~:~ &\mathbf{PSPACE}\hbox{-vollst\"andige Probleme}
\end{align*}

\bigskip

Transitivit\"at der Vollst\"andigkeit:
\[
\left.
\hbox{
\begin{minipage}{5.5cm}
$\mathcal{P}, \mathcal{Q} \in \mathcal{C}$\\
$\mathcal{P}~R\hbox{-vollst\"andig~f\"ur}~\mathcal{C}$\\
$\mathcal{P} \leq_R \mathcal{Q}$
\end{minipage}
}
\right\}
~\Rightarrow~
\mathcal{Q} ~ R\hbox{-vollst\"andig~f\"ur}~\mathcal{C}
\]

\bigskip

Folgerungen:
\begin{align*}
\exists Q : Q ~\mathbf{P}\hbox{-vollst\"andig} \wedge
Q \in \mathbf{L}
& \Rightarrow &
\mathbf{L} = \mathbf{P} \\[5mm]
\exists Q : Q ~\mathbf{P}\hbox{-vollst\"andig} \wedge
Q \in \mathbf{NC}
& \Rightarrow &
\mathbf{NC} = \mathbf{P} \\[5mm]
\exists Q : Q ~\mathbf{NP}\hbox{-vollst\"andig} \wedge
Q \in \mathbf{P}
& \Rightarrow &
\mathbf{P} = \mathbf{NP} \\[5mm]
\exists Q : Q ~\mathbf{PSPACE}\hbox{-vollst\"andig} \wedge
Q \in \mathbf{P}
& \Rightarrow &
\mathbf{P} = \mathbf{PSPACE} \\[5mm]
\exists Q : Q ~\mathbf{PSPACE}\hbox{-vollst\"andig} \wedge
Q \in \mathbf{NP}
& \Rightarrow &
\mathbf{NP} = \mathbf{PSPACE}\end{align*}

\pagebreak

Existenz von vollst\"andigen Problemen:
\begin{itemize}
\item
Es gibt \textbf{P}-vollst\"andige Probleme:
\begin{quote}
\textsc{Circuit Value}
\end{quote}

\item
Es gibt \textbf{NP}-vollst\"andige Probleme:
\begin{quote}
\textsc{Circuit Satisfiability} bzw. 
\textsc{Satisfiability}
\end{quote}

\item
Es gibt \textbf{PSPACE}-vollst\"andige Probleme:
\begin{quote}
\textsc{QBF} = \textsc{Quantified Boolean Formula}
\end{quote}

\end{itemize}

\pagebreak

Weiter Informationen in Stichworten

\begin{itemize}
\item
\textsc{Cnfsat}, \textsc{Clique}, \textsc{TSP}, \textsc{Graph Coloring},
\textsc{Knapsack}, \textsc{Bin Packing}, \textsc{Hamiltonian Path},
\textsc{3dim Matching}, ... 
\\
und hunderte von weiteren Problemen
in Gebieten wie:\\
Graphentheorie und Netzwerke, Mengensysteme, 
Scheduling, Speichern und Suchen, Optimierung,
Algebra und Zahlentheorie, Logik, Automatentheorie,
Programmierung, Spiele, ...\\

\item
Die Vermutung $\textbf{P} \stackrel{?}{\neq} \textbf{NP}$ ist bis heute
weder bewiesen noch widerlegt.\\

\item
Aus $\mathcal{P} \in \textbf{P}$ f\"ur ein einziges 
$\mathcal{P} \in \textbf{NPC}$ w\"urde
bereits $\textbf{P} = \textbf{NP}$ folgen\\

\item
Aus $\textbf{P} = \textbf{NP}$ folgt sofort 
$\textbf{co-NP} = \textbf{NP}$, da ja $\textbf{P} = \textbf{co-P}$ gilt
(Definition von \textbf{P}).\\

\item
Aus $\textbf{co-NP} = \textbf{NP}$ folgt nicht notwendig $\textbf{P} = \textbf{NP}$.\\
\item
Heuristik spricht f\"ur $\textbf{co-NP} \neq \textbf{NP}$ : 
wie soll man sich
``Zeugen'' f\"ur 
$\hbox{\textsc{Clique}}^c$, 
$\hbox{\textsc{TSP}}^c$,
$\hbox{\textsc{Satisfiability}}^c$, ... vorstellen ?
\\
Aber auch diese Vermutung ist bislang unbewiesen.\\


\pagebreak

\item
Aus $\textbf{co-NP} \cap \textbf{NPC} \neq \emptyset$ folgt
$\mathbf{NP} = \textbf{co-NP}$.
\vskip0.5cm
Wegen $\hbox{\textsc{Sat}} \in \textbf{NPC}$ gilt 
$\hbox{\textsc{Taut}} \in \textbf{co-NP}$.
\newline
Das Problem \textsc{Taut} repr\"asentiert die Komplexit\"at des
logischen Schliessens in der Aussagenlogik (Resolutionsmethode
zielt auf Nachweis der Unerf\"ullbarkeit!). 
\newline
[\textsc{Prolog} !?!]
\newline
Beachte:
\begin{align*}
\hbox{\textsc{Sat}} \in \textbf{P} & 
~~~\Leftrightarrow & 
\textbf{P} = \textbf{NP} \Leftrightarrow \hbox{\textsc{Taut}} \in \mathbf{P} \\
\hbox{\textsc{Taut}} \in \textbf{NP} \setminus \textbf{P} & 
~~~\Rightarrow & 
\textbf{P} \neq \textbf{NP}~\wedge~ \textbf{NP} = \textbf{co-NP} \\
\hbox{\textsc{Taut}} \not \in \mathbf{NP} & 
~~~\Rightarrow &
\textbf{P} \neq \textbf{NP}~\wedge~ \textbf{NP} \neq \textbf{co-NP}
\end{align*}\\
\item
Falls $\mathbf{P} \neq \mathbf{NP}$ gilt, muss es \textbf{NP}-Probleme geben,
die weder zu \textbf{P}\  noch zu \textbf{NPC}\  geh\"oren (Satz von Ladner).
\newline
Die drei ``klassischen'' Kandidaten f\"ur 
\[
\mathcal{P} \in \mathbf{NP} \setminus \{\mathbf{P} \cup \mathbf{NPC}\}
\]
waren
\begin{itemize}
\item
\textsc{Primes}
\item
\textsc{Linear Programming}
\item
\textsc{Graph Isomorphism}
\end{itemize}
\textsc{Khachian} hat 1979
$\hbox{\textsc{Linear Programming}} \in \textbf{P}$ gezeigt.
\newline
``$\hbox{\textsc{Primes}} \in \textbf{P}$'' 
wird neuerdings f\"ur durchaus m\"oglich gehalten.

\end{itemize}
\end{document}