Warum bei c) $Y \in NP$?

Question

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!

Answer 1

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)