Polynomialzeitreduktion und Komplexitätsklasse

Question

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 !

Comments

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$

Answer 1

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

Comments

Super vielen Dank, jetzt ist der Groschen auch gefallen !