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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
289 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 !
in BER-AA von uqdme uqdme Lernwillige(r) (250 Punkte)  
0 0
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$

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte

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

von Dozent (10.1m Punkte)  
0 0
Super vielen Dank, jetzt ist der Groschen auch gefallen !
...