Fragen zu den Komplexitätsklassen und Polynomialzeitreduktion

Question

1) Wie ist es also zu verstehen: NP-schwer ist die Teilmenge von NP-vollst, oder ist es eine Teilmenge von NP (wenn ich so ein Diagram zeichnen würde, wie bei der Aufgabe 59).

2) bei der Aufg.teil iii: ist es so zu erklären: wenn P=NP, dann ist C nicht in polyn. Zeit lösbar, weil NP probleme es nicht sind? Aber wieso dann die Aussage P=NP? C ist doch eh NP schwer

3) Aufgabenteil iv: ist es nicht reduzierbar, weil D elemt aus P ist?

 

Danke

 

Answer 1

zu 1): weder noch; siehe Saalübung, letzte Folie

zu 2): allgemeine NP-Probleme können durchaus in Pol.-Zeit lösbar sein!! In NP liegt ja insbesondere auch P, also alle Probleme, die in det. Pol.-Zeit lösbar sind. Die 3. Aussage in der Aufgabe ist NICHT: "C ist nicht in Pol.-Zeit lösbar", sondern: "Wir können aus P=NP und C ist NP-schwer nicht folgern, dass C in Pol.-Zeit lösbar ist." (Möglich ist es aber schon.) Wenn C NP-vollständig wäre, könnten wir aus P=NP folgern, dass C in det. Pol.-Zeit lösbar ist; aber da es NP-schwer ist, kann es beliebig außerhalb von NP liegen und demnach beliebig schwer sein.

zu 3): D ist in Pol.-Zeit reduzierbar auf A und B (denn alle Probleme aus P sind in Pol.-Zeit reduzierbar auf alle anderen Probleme aus NP).

Viele Grüße

Lukas König

Comments

Danke erstmal für die ausführliche Erklärung. Noch einmal zu 3.). Gilt NP = P so folgt, dass jedes NP - vollständige Problem in detpol. zeit lösbar ist.

Wenn C NP - Schwer ist, bedeutet das, dass sich jedes Problem aus NP in polynomieller zeit auf C reduzierbar ist, das C liegt außerhalb von NP. Wenn ich nun festgestellt hätte, dass NP = P gilt,  dann weiß ich doch, dass jedes NP Problem in detpolynomieller Zeit lösbar ist. Ich kann ebenfalls jedes Problem aus NP in polynomieller Zeit auf C reduzieren. Deswegen hätte ich gesagt C ist ebenfalls polynomiell lösbar (obwohl außerhalb von P bzw NP). Liegt mein fehler hier bei meinem Schluss im letzten Satz( da man nur sagen kann aus Q <pol P, P polynomiell lösbar => Q polynomiell lösbar aber NICHT die Umkehrung?)

 

Danke schonma

---

Hallo,

C muss an dieser Stelle nicht polynomiell lösbar sein. Deine Annahme - die aus P = NP folgt - ist ja nur, dass du alle Probleme, die in NP liegen in polynomieller Zeit lösen kann. Da C aber nur NP-schwer und nicht NP-vollständig ist, muss es nicht selbst in NP liegen.

Nur weil du ein polynomiell-lösbares Problem polynomiell auf C reduzieren kannst, heißt das noch nicht, dass C selbst auch polynomiell lösbar ist. Du könntest ja theoretisch auch ein polynomiell-lösbares Problem in polynomieller Zeit in ein sehr viel schwieriges Problem umwandeln, welches nicht mehr polynomiell lösbar ist.

Beste Grüße

Fabian (Tutor)