warum die Aussage, ein NP-schweres Problem lässt sich auf ein NP-schweres Problem reduzieren, falsch?

Question

Wir sagen in Zeile 1, Spalte 1, dass sich ein NP-vollständiges Problem (A) auf ein NP-vollständiges Problem (SAT) reduzieren lässt. Aber warum ist dann in Zeile 4, Spalte 3 die Aussage, ein NP-schweres Problem (A) lässt sich auf ein NP-schweres Problem (B) reduzieren, falsch? Oder können wir davon ausgehen, dass das SAT Problem NP-schwer ist? Daraus würde ich dann schließen, dass Probleme einer Klasse sich nicht auf Probleme derselben Klasse reduzieren lassen! Ist die Annahme richtig?

Answer 1

Alle NP-Vollständigen Probleme sind auch NP-Schwer, insbesondere also auch das SAT-Problem. Grund: die Menge der NP-Vollständigen Probleme ist eine (echte) Teilmenge der Menge der NP-vollständigen Probleme.

Das Kreuz in Zeile 1, Spalte 1 resultiert aus der Tatsache, dass alle NP-vollständige Problem in NP liegen sowie der Definition von NP-vollständig. Das hat nichts mit der Aussage "selbe Klasse lässt sich auf selbe Klasse polynomiell reduzieren" zu tun. Diese Aussage ist im Allgemeinen falsch. Ein Gegenbeispiel für Zeile 4, Spalte 3 ist B -> SAT und A -> nicht entscheidbares, NP-Schweres Problem (solche Probleme existieren). Wenn die Aussage wahr wäre, dann hieße das, dass A über den Umweg SAT doch entscheidbar wäre -> Widerspruch.

Tobias (Tutor)

Comments

Nachdem mir heute im Tut die Frage gestellt wurde, noch ein kleiner zusätzlicher Tipp:

-Es ist NICHT danach gefragt, welche Spalte aus der jeweiligen Zeile folgt, sondern für welche Spalten die Zeile gilt!!!

Bsp aus Zeile 1:

[A   poly. reduzierbar auf SAT]   gilt für [A NP-vollst.] und [A aus NP] .

Falsch ist die Interpretation:

Aus [A     poly. reduzierbar auf   SAT]  folgt [A ist NP-vollst.]

(wie im Tut erwähnt muss, dass nicht sein, denn A kann ja auch ein ganz 'einfaches' Probelm sein ;) )

Liebe Grüße

Bastian (Tutor)