Warum liegen A und B in NP vollständig?

Question

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?

Answer 1

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)