Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

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

+2 Punkte
549 Aufrufe

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 DP, 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?

Gefragt 11, Feb 2016 in BER-AI von utdtz utdtz Eins-Komma-Null-Anwärter(in) (3,110 Punkte)  
Bearbeitet 11, Feb 2016 von utdtz utdtz

Eine Antwort

+1 Punkt
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)
Beantwortet 11, Feb 2016 von ukean ukean Tutor(in) (103,140 Punkte)  
Bearbeitet 11, Feb 2016 von ukean ukean
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ß?
...