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
131 Aufrufe

Hallo,

aus den Tutorien weiß ich, dass A<x B bedeutet, dass A höchstens so schwer ist wie B, B aber vermutlich schwerer zu lösen ist. Siehe dazu Anhang "tut."

Dazu meine Gedanken zur Frage 3 aus den Kontrollfragen, mit der Bitte um Überprüfung:

Nehmen wir an es handelt sich um polzeit Reduktion.  Also A<p B

Wir können eine Lösung für B berechnen , indem wir A durch eine in polzeit berechenbare Funktion f  für den Algo der B löst handhabbar machen können, und diese Lösung dann wieder durch eine Funktion g in polzeit in eine Lösung für A wandeln können. Da f & g nur Faktoren in polynomieller Zeit  hinzufügen, ist dies akzeptabel und damit  A "Höchstes" so schwer wie B. Wieso A nun aber leichter sein soll erschließt sich mir logisch noch nicht....Wäre hier um eine offizielle Lösung dankbar.

Dann noch folgende Frage von mir:

Doch wie passt  die Aussage aus dem Tutorium mit dem Screenshot (Anhang) aus dem Info Buch zusammen, dass Sat <pol 3-Sat ist. Bedeutet das also das 3 -SAT schwerer zu lösen ist als SAT.

3- Sat ist ja eine Einschränkung der Literale, der das Problem doch eigentlich leichter machen sollte....zumindest erscheint mir das intuitiv so.

Ich hoffe es ist klar was ich damit meine. 

 

Lieben Dank für die Mühe und Antworten

Grüße

Tut:

Tut

Infobuch:

in Kapitel 7 von  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

aus den Tutorien weiß ich, dass A<x B bedeutet, dass A höchstens so schwer ist wie B, B aber vermutlich schwerer zu lösen ist. Siehe dazu Anhang "tut."

"Vermutlich" stimmt nicht. Über die Wahrscheinlichkeit ist keine Aussage getroffen. Es stimmt aber, dass $A$ bis auf die durch $x$ bestimmten Faktoren (also normalerweise polynomielle, wenn $x=pol$) nicht schwerer sein kann als $B$. "Ein bisschen" schwerer also schon, aber nicht "viel" schwerer.

Wir können eine Lösung für B berechnen , indem wir A durch eine in polzeit berechenbare Funktion f  für den Algo der B löst handhabbar machen können, und diese Lösung dann wieder durch eine Funktion g in polzeit in eine Lösung für A wandeln können. Da f & g nur Faktoren in polynomieller Zeit  hinzufügen, ist dies akzeptabel und damit  A "Höchstes" so schwer wie B. Wieso A nun aber leichter sein soll erschließt sich mir logisch noch nicht....Wäre hier um eine offizielle Lösung dankbar.

Der erste Satz ist genau falsch herum. $A \leq_{pol} B$ heißt, dass wir $A$ berechnen können, indem wir den Umweg über $B$ gehen. Die Schlussfolgerung ist dann, dass es dieses eine Lösungsverfahren für $A$ auf jeden Fall gibt. Wenn uns nichts anderes einfällt, machen wir eben den Umweg über $B$ und haben $A$ gelöst, wobei wir höchstens so viele Ressourcen verbraucht haben, wie der Algorithmus für $B$ benötigt (plus ein bisschen pol. Overhead). Daher "höchstens so schwer". Aber das ist ja nur eine Möglichkeit, es kann ja auch andere Algorithmen geben, die $A$ noch effizienter lösen. Daher sagen wir, $A$ ist nicht schwerer als $B$, aber unter Umständen leichter.

Was Ihre $3$-SAT / SAT - Frage angeht, da haben Sie absolut recht: $3$-SAT ist natürlich nicht schwerer als SAT. Mit der Reduktion zeigen wir aber auch das umgekehrte: SAT ist auch nicht schwerer als $3$-SAT (bis auf pol. Faktoren). In diesem Fall wissen wir also, dass SAT und $3$-SAT ungefähr gleich schwer sind. Das gilt so für alle $NP$-vollständigen Probleme.

Für zwei $NP$-vollständigen Probleme $X, Y$ gilt stets: $$X \leq_{pol} Y$$

von Dozent (10.1m Punkte)  
Bearbeitet von
0 0
Jetzt bin ich ein bisschen verwirrt.

"Mit der Reduktion zeigen wir aber auch das umgekehrte: SAT ist auch nicht schwerer als 3-SAT (bis auf pol. Faktoren)."

Ist das nur ein Spezialfall, weil beide Probleme NP-vollständig sind?
 
Sollte das nämlich Allgemein gelten, würde ich hier ein Widerspruch vermuten:

"Daher sagen wir, A ist nicht schwerer als B, aber unter Umständen leichter."

Denn: Angenommen ich finde eine effizienteren Algorithmus für A. Dann könnte ich B auch über den Umweg über A lösen. Wodurch dann B nicht schwerer als A sein kann. Dadurch sind dann aber beide Probleme genau gleich schwer und A kann nicht leichter als B sein.

Schonmal danke!
0 0
Natürlich ist das ein Spezialfall, so wie in der Arithmetik $x=y$ ein Spezialfall von $x \leq y$ ist. Warum sollten Sie denn allgemein $B$ über den Umweg $A$ lösen können? Wenn $A \leq B$ gilt, dann können Sie $A$ über den Umweg $B$ lösen, aber nicht umgekehrt. Sind $A$ und $B$ $NP$-vollständig, dann gilt eben beides.
0 0
Ja das war jetzt in der Tat ein Tippfehler bei mir. Ich meinte natürlich "A" statt "B" im ersten Satz.

Lieben Dank für die Erklärung. Hat mir geholfen.

Grüße
...