Kann ich ein NP-schweres Problem auf ein NP-vollständiges Problem reduzieren?

Question

Hallo,

die erste Aussage "Wenn A NP-schwer ist, so kann es in Polynomialzeit auf jedes NP-vollständige Problem reduziert werden." ist laut Lösung falsch.

In Aufgabe BER-AB (S.83 Aufgabe 91) ist die letzte Aussage "D ist in Polynomialzeit reduzierbar auf C, aber nicht auf A. " falsch, wobei D∈P, C ist NP-schwer, A ist NP-vollständig.

Als Ergänzung in der Lösung steht: "D ist sowohl auf C als auch auf A in Polynomialzeit reduzierbar. "

Das heißt: einmal konnte ich ein NP-schweres Problem nicht auf ein NP-vollständiges Problem reduzieren (A auf jedes NP-vollständige), ein anderes Mal konnte ich es. (D auf A)

Wieso ist das so? Was kann man sich allgemein für die Reduzierbarkeit von NP-schweren Problemen auf NP-vollständige Probleme merken?

Answer 1

Hallo utdtz,

du musst immer auf die "Richtung" achten. In einfachen Worten gesagt, kannst du zwar ein leichtes Problem auf ein Problem das schwerer ist reduzieren, umgekehrt funktioniert das aber natürlich nicht.

Im ersten Teil geht es darum ein NP-schweres Problem auf ein NP-vollständiges in Polynomialzeit zu reduzieren. NP-schwere Probleme können beliebig schwer sein und sind zum Teil auch nicht- oder nur semientscheidbar. NP-vollständige Probleme haben neben der NP-schwere allerdings die "Zusatzeigenschaft", dass sie selbst in NP liegen und demnach nichtdeterministisch in polynomieller Zeit lösbar sind .

Es gibt also NP-schwere Probleme (z.B. ein NP-vollständiges), das sich auf ein anderes NP-vollständiges Problem reduzieren lässt (z.b. SAT auf CLIQUE).  Ein beliebiges NP-schweres Problem in polynomieller Zeit auf jedes NP-vollständige Problem zu reduzieren funktioniert aber nicht.

Im zweiten Fall dagegen hast du ein recht einfach zu lösendes Problem aus der Klasse P, dass du auf ein schweres Problem (Np-schwer bzw. NP vollständig) reduzierst.

Eine Merkregel wäre auch: Wenn sich A in pol. Zeit auf B reduzieren lässt, kann A "höchstens so schwer sein" wie B.

Viele Grüße,

Tim (Tutor)

Comments

Entschuldigung, ich hatte mich verlesen, in Aufgabe BER-AB ist alles klar, weil ja dort einmal P auf NP-schwer reduziert wird (D auf C) und einmal P auf NP-vollständig (D auf A).

Also ist es so, dass man "nichtdeterministisch in Polynomialzeit lösbar" gut auf "nichtdeterministisch in Polynomialzeit lösbar" reduzieren kann [so wie in der vierten Aussage (richtig) "B lässt sich auf SAT reduzieren." (B: NP-schwer, ndet in Polynomialzeit lösbar auf SAT: NP-vollständig)], jedoch NP-schwer auf NP-vollständig nicht, weil ich nichts Näheres über das NP-schwere Problem weiß?