Vergleich von Problemen

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).