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

BER-AI: NP-Schwer reduzierbar auf SAT, NP-Vollständig in Pol lösbar

+2 Punkte
59 Aufrufe

Hallo,

in Aufgabe 93 steht,

1) dass B (NP-Schwer) reduzierbar auf SAT ist. Wie kann das sein?

2) dass wenn P=NP und C Element von P, dann ist C NICHT NP-Vollständig. Ist NP-vollständig dann trotzdem in Polymnialzeit lösbar?

Gruß

 

Gefragt 7, Feb 2016 in Band I, Kapitel 10 von uagll uagll Lernwillige(r) (1,100 Punkte)  
Zu 1): Was heißt das denn: "B ist NP-schwer und nichtdeterministisch in Polynomialzeit lösbar"? Was ist B dann - wenn Sie das wissen, wissen Sie auch, warum es auf SAT reduzierbar ist.

Eine Antwort

0 Punkte
Was 2) angeht: Das bezieht sich auf eine sehr spezielle Eigenschaft von NP-vollständigkeit - in der Klausur hätten Sie so eine schwierige Frage nicht lösen müssen.

Die grundsätzliche Aussage, die nicht GANZ, aber IM KERN richtig ist, lautet:
$$P=NP \Rightarrow \mbox{ alle Probleme aus $NP$ sind $NP$-vollständig}$$
Diese Aussage stimmt deshalb nicht ganz, weil es die beiden trivialen Probleme
$$X = \emptyset \mbox{ bzw. } X = E^\star \in P=NP$$
gibt, die auch dann nicht $NP$-vollständig wären. Auch wenn man das oft vernachlässigen kann, ist die Aussage, wie sie in der Multiple-Choice-Aufgabe steht, strenggenommen nicht korrekt, und deshalb haben wir das auch entsprechend als falsch angekreuzt und erklärt.

Viele Grüße

Lukas König
Beantwortet 8, Feb 2016 von Lukas König Dozent (10,065,100 Punkte)  
...