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!
 

 

Warum bei c) $Y \in NP$?

–1 Punkt
56 Aufrufe
Hallo,

 

sofern ich den Graphen richtig lese: Müsste es nicht $Y \in NP\mbox{-vollständig}$(!) heißen, damit die Aussage so richtig ist?

Denn laut Graph: $Y \in NP$ ist nicht zwangsläufig $Y \in NP\mbox{-schwer}$. Oder ist das Lesen als Mengen nicht korrekt...

 

VG & danke!
Gefragt 16, Jan 2015 in BER-AA von uceae uceae Lernwillige(r) (110 Punkte)  
Bearbeitet 16, Jan 2015 von Lukas König

Eine Antwort

0 Punkte

Hallo!

Nein, die Musterlösung ist korrekt, denn die Regel lautet:

Ein Problem X ist genau dann NP-schwer, wenn sich alle Probleme Y aus NP darauf reduzieren lassen.

Es geht hier also nicht darum, dass die Probleme Y selbst NP-schwer sein müssen, sondern dass man sie alle durch Polynomialzeitreduzierbarkeit auf ein NP-schweres Problem X überführen kann.

 

Ich hoffe, diese kleine Denkanstoß hilft dir weiter!

Gruß, Janine (Tutorin)

Beantwortet 16, Jan 2015 von uedqi uedqi Tutor(in) (108,510 Punkte)  
...