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

5 Pluspunkte 0 Minuspunkte
128 Aufrufe
Wenn man CLIQUE in polynomieller Zeit auf A bzw B bzw F reduzieren kann, warum kann man dann für A und B schließen, dass sie in NP vollständig liegen und nicht wie für F nur, dass sie in NP schwer liegen?
bezieht sich auf eine Antwort auf: Aufgabe 5
in 2012-H-05 von uxduy uxduy Lernwillige(r) (470 Punkte)  

1 Eine Antwort

4 Pluspunkte 0 Minuspunkte
 
Beste Antwort

Hallo uxduy!
 

Um A und B richtig einsortieren zu können, genügt es nicht, nur die erste Zeile zu betrachten, sondern auch die zweite Zeile ist hier zu beachten!

Aus der ersten Zeile folgt, dass CLIQUE polynamialzeit-reduzierbar auf A ist, A wiederum auf B und B wiederum auf F. Wir wissen (bzw. es ist in der Aufgabenstellung gegeben), dass CLIQUE selbst NP-vollständig ist. Wenn wir also CLIQUE in polynomieller Zeit zunächst auf A reduzieren können, dann muss A mindestens so schwierig oder schwieriger sein als CLIQUE. Das bedeutet, dass wir zunächst davon ausgehen, dass A NP-schwer ist, denn die Definition von NP-schweren Problemem ist ja gerade, dass sich alle Probleme aus NP (also auch die NP-vollständigen Probleme wie hier CLIQUE) darauf in polynomieller Zeit reduzieren lassen. Gleiches gilt für B und F (wegen der Transitivität der polynomiellen Reduzierbarkeit, siehe Tutorium 3 , Aufgabe 6). Damit gehen wir also bis jetzt davon aus, dass A, B und F alle drei in NP-schwer liegen.

So, und nun kommt aber die zweite gegebene Zeile der Aufgabenstellung hinzu: B ist Element von NP. Die Schnittmenge von NP-schwer und NP ist gerade NP-vollständig, also wissen wir jetzt, dass B in NP-vollständig liegt. Und da A in polynomieller Zeit auf B reduziert werden kann, kann A nicht schwerer sein als B, dh. auch A liegt in NP-vollständig.

Die Lage von F können wir nicht weiter eingrenzen, da es eben bildlich gesprochen "ganz rechts" in der Reduzierbarkeits-Kette steht und wir damit nur wissen, dass es mindestens so schwer ist wie NP-vollständig.

Ich hoffe, das hilft dir weiter!

Viele Grüße,
Janine (Tutorin)

von uedqi uedqi Tutor(in) (109k Punkte)  
ausgewählt von
Wenn man die B=NP erst betrachtet:
...