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 minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort 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 pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 1 Minuspunkt
117 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$.
...