Fachrat Informatik - Forum

Alle Probleme aus NP lassen sich *auf* SAT reduzieren. Wenn man nun SAT *auf* ein anderes Problem reduziert, dann ist dieses Problem dann natürlich NP-hart.
Jedes Problem, welches sich *auf* SAT reduzieren lässt, ist selber in NP enthalten (da SAT in NP enthalten ist).

In der Aufgabe wird behauptet, dass sich jedes Problem L, welches sich auf SAT reduzieren lässt, in Zeichen L <=_m^P SAT, NP-hart wäre. Das ist natürlich erstmal so nicht korrekt, weil wir lediglich aus L <=_m^P SAT folgern können, dass L in NP liegt.

Ändert man die Behauptung zu "Jedes Problem auf welches man von SAT aus reduzieren kann, ist NP-hart", dann wäre diese korrekt. Beachte hierbei die Änderung des "Blickwinkels".
A reduziert man auf B bedeutet A <=_m^P B.
Auf A reduziert man von B aus bedeutet B <=_m^P A.
Das Reduktionssymbol "<=_m^P" kann man folglich umgangssprachlich als "ist reduzierbar auf" lesen.

Klar geworden?

Beste Grüße,
Arne Meier