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

3 Pluspunkte 0 Minuspunkte
81 Aufrufe
Ich verstehe die Aufgabe nicht. wieso liegt F in NP und ist nicht NP vollständig? Wieso können wir über F eine spezifischere Aussage als über D machen? Wieso liegt C sicher in P?
in 2012-H-05 von updjl updjl Lernwillige(r) (340 Punkte)  
Kategorie geändert von

2 Antworten

2 Pluspunkte 0 Minuspunkte
Unsere einzige Information über F ist hier, dass CLIQUE polynomialzeitreduzierbar auf F ist. Da CLIQUE NP-vollständig ist, also unter anderem NP-schwer ist, können wir folgern, dass F ebenfalls NP-schwer ist also dass jedes Problem aus NP polynomialzeitreduzierbar auf F ist. Dies ist möglich, da wir wissen, dass bereits jedes Problem aus NP auf CLIQUE polynomialzeitreduzierbar ist. Über die Zugehörigkeit von F zu der Menge NP (bzw. einer anderen Menge) haben wir jedoch keine Information. Deshalb liegt es nur in NP-schwer.

Von D wissen wir nur, dass PRIMES polynomialzeitreduzierbar auf D ist. Das grenzt jedoch nicht weiter ein, in welcher Klasse das Problem liegt, weshalb es ganz außen eingeordnet ist.

C liegt in P, da es auf PRIMES polynomialzeitreduzierbar ist. Ensprechend muss es "mindestens so leicht wie PRIMES sein". Folglich wird es in die Klasse P eingeordnet

Grüße,
Lukas (Tutor)
von uwdll uwdll Tutor(in) (102k Punkte)  
1 Pluspunkt 0 Minuspunkte
Weil Clique NP-vollständig ist und Clique in Pol-Zeit auf F reduziert werden kann, ist F NP-schwer. Denn alle Probleme in NP-vollständig haben die Eigenschaft, dass alle Probleme aus NP auf sie reduzierbar sind - und da die Polynomialzeitreduktion eine transitive Relation ist, ist auch jedes Problem aus NP auf F reduzierbar. Über D können wir diese Aussage nicht treffen, weil PRIMES nicht NP-vollständig ist. Allerdings steht nirgends, dass F NICHT in NP ist, das ist nur aus den gegebenen Aussagen nicht ableitbar - aber auch nicht widerlegbar. Ebenso könnte auch D NP-schwer sein oder in NP oder sogar P liegen - wir können das nur nicht aus den Aussagen ableiten.

C ist in Pol-Zeit reduzierbar auf PRIMES, ist also "höchstens so schwer wie" PRIMES. Da PRIMES in P ist, ist auch C in P.
von Dozent (10.1m Punkte)  
Warum liegen A und B in NP vollständig?
...