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.)

Schöne Ferien!
 

 

Wieso ist B NP-vollständig?

–1 Punkt
25 Aufrufe
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?
bezieht sich auf eine Antwort auf: Begründungen zu den Aussagen richtig?
Gefragt 22, Okt 2014 in BER-AI von utdbu utdbu Tutor(in) (106,580 Punkte)  

Eine Antwort

0 Punkte

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)

 

Beantwortet 22, Okt 2014 von utdbu utdbu Tutor(in) (106,580 Punkte)  
...