Warum ist F nicht in p(E*)?

Question

Bei D heisst es ,dass es ganz außen stehen muss, da keine weiteren Infos ( )vorhanden sind. Wieso gilt das gleiche nicht auch für F?

Danke!

Answer 1

Na für $F$ wissen wir doch immerhin, dass es $NP$-schwer ist. Das liegt daran, dass ein $NP$-vollständiges Problem, nämlich $CLIQUE$, darauf reduziert werden kann. Auf $D$ wurde dagegen von den bekannten Problemen nur $PRIMES$ reduziert, was nicht $NP$-vollständig ist und daher keine weiteren Informationen liefert.

Answer 2

Hallo,

da B in NP liegt und gilt: B <pol F muss F laut Definition in NP-schwer liegen.

Im Hinweis der Aufgabe ist auch nochmal aufgeführt, dass du hier nur zw. NP-vollständig und nicht-NP-vollständig unterscheiden musst.

Grüße

Comments

Bisschen zu spät hat sich wohl erledigt.

---

Das ist nicht der Punkt! $B$ muss nicht nur in $NP$ liegen, sondern $NP$-vollständig (bzw. genauer $NP$-schwer) sein. Denn $PRIMES$ liegt ja auch in $NP$.