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!
 

 

Fragen zu den Komplexitätsklassen und Polynomialzeitreduktion

–1 Punkt
249 Aufrufe

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

 

Gefragt 15, Nov 2014 in BER-AB von uyctv uyctv Info-Genie (19,250 Punkte)  

Eine Antwort

0 Punkte
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
Beantwortet 15, Nov 2014 von uyctv uyctv Info-Genie (19,250 Punkte)  
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)
...