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

Question

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ß

 

Comments

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.

Answer 1

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