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!
 

 

Polynomialzeitreduktion und Komplexitätsklasse

+1 Punkt
60 Aufrufe
Hallo ich hätte eine Verständnisfrage zur  Polynomialzeitreduktion und den Komplexitätsklasse.

Im Lehrbuch wird an zwei Stellen( Seite 338 Typische Anwendungsfälle der Polynomialzeitreduktion) darauf hingedeutet, dass wenn ein Problem X polynomialzeitreduzierbar auf ein Problem Y ist, beide Probleme in der selben Komplexitätsklasse liegen müssen.

Der erste Fall ist für mich intuitiv verständlich.

Ich habe mir das so erklärt, dass wenn die Lösung des Problems X selbst mit dem Umweg über Y "nur" polynomielle Zeit beansprucht, dann kann der direkte Weg nicht wesentlich länger (mehr Zeit) beanspruchen und somit müssen die Probleme in der gleichen Klasse liegen

Aber den Anwendungsfall 2 verstehe ich nicht so wirklich.  Nur weil X NICHT in P liegt aber auf Y reduzierbar ist, heißt das doch nciht automatisch, dass Y auch NICHT in P liegt?

 

Vielen Dank für die Antwort !
Gefragt 15, Okt 2017 in BER-AA von uqdme uqdme Lernwillige(r) (250 Punkte)  
Was den Fall 1 angeht, haben Sie recht. $Y \in P \wedge X \leq_{pol} Y \implies X \in P$, denn man kann $X$ lösen, indem man den Umweg über $g(Y(f(w)))$ geht. Da all diese Operationen in Polzeit möglich sind, ist der Gesamtprozess auch in $P$. Und Fall zwei ist einfach die logische Umkehrung dieser Aussage: $X \notin P \implies Y \notin P \vee X \nleq_{pol} Y$

Eine Antwort

+1 Punkt

Nur weil X NICHT in P liegt aber auf Y reduzierbar ist, heißt das doch nciht automatisch, dass Y auch NICHT in P liegt?

Doch, genau das heißt es. Denn wenn $$X \leq_{pol} Y$$ gilt, dann ist $Y$ (bis auf polynomielle Faktoren) mindestens so schwer wie $X$. Könnten wir $Y$ in det. Polynomialzeit lösen, dann hätten wir über die Reduktion auch automatisch einen Polzeit-Algorithmus für $X$ (einfach aus der Eingabe $w$ für $X$ in Polzeit die Eingabe $f(w)$ für $Y$ berechnen und dann den Polzeit-Algorithmus für $Y$ laufen lassen (und dann eventuell noch die Lösung von $Y$ durch $g$ in eine Lösung für $X$ rücküberführen); all diese Schritte kosten Polynomialzeit, also bleiben wir insgesamt auch in Polynomialzeit).

Beantwortet 15, Okt 2017 von Lukas König Dozent (10,065,090 Punkte)  
Super vielen Dank, jetzt ist der Groschen auch gefallen !
...