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

2 Pluspunkte 0 Minuspunkte
798 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ß?
...