Kontrollfrage 3 Kpt. 7 Infobuch - Reduzierbarkeit

Question

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:

Infobuch:

Answer 1

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$$

Comments

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!

---

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.

---

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