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

1 Pluspunkt 0 Minuspunkte
97 Aufrufe

Wir sagen in Zeile 1, Spalte 1, dass sich ein NP-vollständiges Problem (A) auf ein NP-vollständiges Problem (SAT) reduzieren lässt. Aber warum ist dann in Zeile 4, Spalte 3 die Aussage, ein NP-schweres Problem (A) lässt sich auf ein NP-schweres Problem (B) reduzieren, falsch? Oder können wir davon ausgehen, dass das SAT Problem NP-schwer ist? Daraus würde ich dann schließen, dass Probleme einer Klasse sich nicht auf Probleme derselben Klasse reduzieren lassen! Ist die Annahme richtig?

in 2009-H-04 von updkn updkn Info-Genie (6.6k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte

Alle NP-Vollständigen Probleme sind auch NP-Schwer, insbesondere also auch das SAT-Problem. Grund: die Menge der NP-Vollständigen Probleme ist eine (echte) Teilmenge der Menge der NP-vollständigen Probleme.

Das Kreuz in Zeile 1, Spalte 1 resultiert aus der Tatsache, dass alle NP-vollständige Problem in NP liegen sowie der Definition von NP-vollständig. Das hat nichts mit der Aussage "selbe Klasse lässt sich auf selbe Klasse polynomiell reduzieren" zu tun. Diese Aussage ist im Allgemeinen falsch. Ein Gegenbeispiel für Zeile 4, Spalte 3 ist B -> SAT und A -> nicht entscheidbares, NP-Schweres Problem (solche Probleme existieren). Wenn die Aussage wahr wäre, dann hieße das, dass A über den Umweg SAT doch entscheidbar wäre -> Widerspruch.

Tobias (Tutor)

von updkn updkn Info-Genie (6.6k Punkte)  
1 0
Nachdem mir heute im Tut die Frage gestellt wurde, noch ein kleiner zusätzlicher Tipp:

-Es ist NICHT danach gefragt, welche Spalte aus der jeweiligen Zeile folgt, sondern für welche Spalten die Zeile gilt!!!

Bsp aus Zeile 1:

[A   poly. reduzierbar auf SAT]   gilt für [A NP-vollst.] und [A aus NP] .

Falsch ist die Interpretation:

Aus [A     poly. reduzierbar auf   SAT]  folgt [A ist NP-vollst.]

(wie im Tut erwähnt muss, dass nicht sein, denn A kann ja auch ein ganz 'einfaches' Probelm sein ;) )

Liebe Grüße

Bastian (Tutor)
Spalte 3- Zeile 3&4
...