Id: reduktion.tex,v 1.1 2003/10/23 16:27:18 joe Exp
Man kann Schwierigkeit von Problemen untereinander vergleichen.
Definition: falls es eine (wenig aufwendige) Funktion gibt, so daß für alle gilt: ist Lösung von ist Lösung von .
Wenn und (leicht) lösbar, dann auch (leicht) lösbar.
Man kann zeigen: Halteproblem PCP.
Nach Kontraposition (Umkehrschluß) folgt: Halteproblem algorithmisch unlösbar PCP algorithmisch unlösbar.
Indiz: sehr kleine und trotzdem schwere PCP-Instanzen (d. h. mit sehr langer Lösung).