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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 1 Minuspunkt
102 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!

in 2012-H-05 von ujeuq ujeuq Tutor(in) (100k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte
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.
von Dozent (10.1m Punkte)  
0 Pluspunkte 0 Minuspunkte

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

von ulefs ulefs Tutor(in) (102k Punkte)  
0 0
Bisschen zu spät hat sich wohl erledigt.
0 0
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$.
...