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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

2 Pluspunkte 0 Minuspunkte
723 Aufrufe

Hallo,

die erste Aussage "Wenn A NP-schwer ist, so kann es in Polynomialzeit auf jedes NP-vollständige Problem reduziert werden." ist laut Lösung falsch.

In Aufgabe BER-AB (S.83 Aufgabe 91) ist die letzte Aussage "D ist in Polynomialzeit reduzierbar auf C, aber nicht auf A. " falsch, wobei DP, C ist NP-schwer, A ist NP-vollständig.

Als Ergänzung in der Lösung steht: "D ist sowohl auf C als auch auf A in Polynomialzeit reduzierbar. "

Das heißt: einmal konnte ich ein NP-schweres Problem nicht auf ein NP-vollständiges Problem reduzieren (A auf jedes NP-vollständige), ein anderes Mal konnte ich es. (D auf A)

Wieso ist das so? Was kann man sich allgemein für die Reduzierbarkeit von NP-schweren Problemen auf NP-vollständige Probleme merken?

in BER-AI von utdtz utdtz Eins-Komma-Null-Anwärter(in) (3.1k Punkte)  
Bearbeitet von utdtz utdtz

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
Hallo utdtz,

du musst immer auf die "Richtung" achten. In einfachen Worten gesagt, kannst du zwar ein leichtes Problem auf ein Problem das schwerer ist reduzieren, umgekehrt funktioniert das aber natürlich nicht.

Im ersten Teil geht es darum ein NP-schweres Problem auf ein NP-vollständiges in Polynomialzeit zu reduzieren. NP-schwere Probleme können beliebig schwer sein und sind zum Teil auch nicht- oder nur semientscheidbar. NP-vollständige Probleme haben neben der NP-schwere allerdings die "Zusatzeigenschaft", dass sie selbst in NP liegen und demnach nichtdeterministisch in polynomieller Zeit lösbar sind .

Es gibt also NP-schwere Probleme (z.B. ein NP-vollständiges), das sich auf ein anderes NP-vollständiges Problem reduzieren lässt (z.b. SAT auf CLIQUE).  Ein beliebiges NP-schweres Problem in polynomieller Zeit auf jedes NP-vollständige Problem zu reduzieren funktioniert aber nicht.

Im zweiten Fall dagegen hast du ein recht einfach zu lösendes Problem aus der Klasse P, dass du auf ein schweres Problem (Np-schwer bzw. NP vollständig) reduzierst.

Eine Merkregel wäre auch: Wenn sich A in pol. Zeit auf B reduzieren lässt, kann A "höchstens so schwer sein" wie B.

Viele Grüße,

Tim (Tutor)
von ukean ukean Tutor(in) (103k Punkte)  
Bearbeitet von ukean ukean
0 0
Entschuldigung, ich hatte mich verlesen, in Aufgabe BER-AB ist alles klar, weil ja dort einmal P auf NP-schwer reduziert wird (D auf C) und einmal P auf NP-vollständig (D auf A).

Also ist es so, dass man "nichtdeterministisch in Polynomialzeit lösbar" gut auf "nichtdeterministisch in Polynomialzeit lösbar" reduzieren kann [so wie in der vierten Aussage (richtig) "B lässt sich auf SAT reduzieren." (B: NP-schwer, ndet in Polynomialzeit lösbar auf SAT: NP-vollständig)], jedoch NP-schwer auf NP-vollständig nicht, weil ich nichts Näheres über das NP-schwere Problem weiß?
...