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 ist F nicht in p(E*)?

0 Punkte
92 Aufrufe

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

Danke!

Gefragt 12, Feb 2017 in 2012-H-05 von ujeuq ujeuq Tutor(in) (100,460 Punkte)  

2 Antworten

0 Punkte
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.
Beantwortet 12, Feb 2017 von Lukas König Dozent (10,065,100 Punkte)  
0 Punkte

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

Beantwortet 12, Feb 2017 von ulefs ulefs Tutor(in) (101,780 Punkte)  
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$.
...