%% -*- mode: latex; TeX-master: "informatik.tex"; -*-

\begin{slide}{Vergleich von Problemen}

\kopf{$ $Id: reduktion.tex,v 1.1 2006-10-09 13:24:19 waldmann Exp $ $}

Man kann Schwierigkeit von Problemen untereinander vergleichen.

Definition: $P_1 \le P_2$ falls es eine (wenig aufwendige) Funktion $f$ gibt,
so daß für alle $x$ gilt: $x$ ist Lösung von $P_1$ 
$\iff$ $f(x)$ ist Lösung von $P_2$.

Wenn $P_1 \le P_2$ und $P_2$ (leicht) lösbar,
dann auch $P_1$ (leicht) lösbar.

Man kann zeigen: Halteproblem $\le$ PCP.

Nach Kontraposition (Umkehrschluß) folgt:
Halteproblem algorithmisch unlösbar $\Rightarrow$
PCP algorithmisch unlösbar.

Indiz: sehr kleine
und trotzdem schwere PCP-Instanzen
(d. h. mit sehr langer Lösung).

\end{slide}

