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.)

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

+1 Punkt
64 Aufrufe

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?

Gefragt 10, Okt 2015 in 2009-H-04 von updkn updkn Info-Genie (6,630 Punkte)  

Eine Antwort

+1 Punkt

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)

Beantwortet 10, Okt 2015 von updkn updkn Info-Genie (6,630 Punkte)  
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)
Spalte 3- Zeile 3&4
...