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 liegen A und B in NP vollständig?

+5 Punkte
106 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
Gefragt 11, Feb 2016 in 2012-H-05 von uxduy uxduy Lernwillige(r) (470 Punkte)  

Eine Antwort

+4 Punkte
 
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)

Beantwortet 11, Feb 2016 von uedqi uedqi Tutor(in) (108,510 Punkte)  
ausgewählt 16, Sep 2016 von Lukas König
Wenn man die B=NP erst betrachtet:
...