Wieso ist B NP-vollständig?

Question

Nun ist mir nur noch eine Sache unklar.

Ihr redet beide bei 3) von B als NP-vollständig, aber laut Aufgabenstellung ist B doch NP-schwer. Woraus folgert ihr, dass es dann auch NP-vollständig ist?

" NP-Vollständig bedeutet, dass das Problem sowohl NP-Schwer ist, als auch in NP liegt." Aber das heißt doch, dass hier eigntlich doch zwischen NP-schwer und vollständig unterschieden werden muss, oder?

Oder wird NP-schwer durch die Aussage "und in nichtdeterministischer Poly.zeit berechenbar" zu NP-vollständig?

Answer 1

Richtig! Dadruch, dass B sowohl NP schwer ist, also auch "nichtdeterministisch in Polynomialzeit lösbar" ist (also selbst in NP liegt), ist das Problem automatisch NP-vollständig. Das ist ja gerade die Definition von NP-vollständigen Problemen.

Du musst natürlich trotzdem zwischen NP-schweren und NP-vollständigen Problemen unterscheiden. NP-vollständige Probleme sind eine Teilmenge von NP-schweren Problemen.

Gruß

Lukas (Tutor)