Was bedeutet die Aussage, dass alle Probleme in P gleichwertig sind bzw. was bedeutet die Relation L1 <=p L2?
Was heißt es:
man kann jedes Problem in P auf jedes andere Problem in P reduzieren
?
Angenommen als Beispiel:
- L1 ist die Entscheidung, ob eine Zahl z1 gerade ist
- L2 ist die Entscheidung ob eine Zahl z2 prim ist
Ich kann nun spaßhalber eine Reduktion von L1 -> L2 machen, indem ich
zuest L1(z1) löse und wenn das Ergebnis
- ja ergibt, füttere ich L2 mit dem Input 3
- nein ergibt, füttere ich L2 mit dem Input 6
Dann habe ich L1 in Polyzeit auf L2 reduziert: man schreibt
bzw. man sagt
" L2 ist mindestens so schwierig wie L1"
Ich könnte aber auch umgekehrt eine Reduktion von L2 -> L1 machen, indem ich
zuest L2(z2) löse (wie auch immer, aber eben in Polyzeit) und wenn das Ergebnis
- ja ergibt, füttere ich L1 mit dem Input 2
- nein ergibt, füttere ich L1 mit dem Input 1
Dann würde ich schreiben können:
bzw. sagen
L1 ist mindestens so schwierig wie L2"
Das würde bedeuten, dass P1 und P2 gleich schwierig sind, was aber klarerweise nicht der Fall ist. Hab ich da was falsch verstanden?
Wie ist das also diese Notation zu interpretrieren?? Irgendwas stimmt doch hier nicht...wo bin ich falsch abgebogen?
Korrektur:
zuest L1(z1) löse und wenn das Ergebnis
- ja ergibt, füttere ich L2 mit dem Input 3
- nein ergibt, füttere ich L2 mit dem Input 6
ist besser, denn 2 ist auch eine Primzahl. Das ändert aber nichts an der Frage.
2 Antworten
Du hast es richtig verstanden. Die Probleme gelten hier als gleich schwer, wenn sich die Lösungsschrittzahl nur polynomiell unterscheidet. Dabei kann es durchaus sein, dass ein Problem in linear vielen, ein anderes jedoch in kubisch vielen Schritten gelöst werden kann, sie beide aber dennoch als gleich schwer gelten. Ist natürlich nicht gerade die praxisrelevanteste Sicht, aber in der Komplexitätstheorie sehr ergiebig.
Ach ja, abgesehen davon, dass 2 und 3 beides Primzahlen sind ^^
Ach ja, abgesehen davon, dass 2 und 3 beides Primzahlen sind
ja, das war zu schnell geschossen: hab meinen Beitrag korrigieren lassen. Aber ist klar, was ich gemeint habe: Nimm statt 2 halt 6
Es sagt nichts über die genaue Komplexität aus, sondern über die Komplexitätsklasse. Man abstrahiert hier, da sich alle Polynome grundsätzlich sehr ähnlich verhalten. Das ist dann äquivalent dazu, dass es eine polynomielle Reduktion gobt.
Im Falle von P wirkt das tatsächlich trivial, aber bei NP liefert das interessante Resultate bzgl. Vollständigkeit.
Ich bin hier nur ein Laie: kannst du das unten stehende Kommentar von Malte314 beurteilen? Er meint nämlich, dass mein Beispiel keine Reduktion wäre - so hab ich es aber gelernt. Es ist in meinen Augen nur keine praktisch sinnvolle Reduktion...
Das sind keine Reduktionen. Eine Reduktion ermöglicht es, ein Problem vermittels eines anderen zu entscheiden. Man »reduziert« also L1(x) auf L2(f(x)) wobei f(x) die Reduktion ist. Für die Frage, ob ein x in L1 ist, transformiert man es also in eine Mögliche Instanz (das macht die Funktion f) und stellt die Frage an L2.
Dabei steht es einem bei einer polynomiellen Reduktion aber durchaus offen, das Problem innerhalb der Transformation zu lösen, und auf triviale Instanzen abzubilden, solange dies in Polyzeit geschieht. Also doch, es ist eine poly-Reduktion.
Aber nicht das Problem selbst, dann kann man nicht mehr von einer Reduktion sprechen. Ich löse das Problem PRIM per Reduktion auf das Problem GERADE, indem ich PRIM löse und entweder 1 oder 2 an GERADE stelle? Ergibt keinen Sinn.
Es ist eine total berechenbare Funktion f, die jede Instanz I auf f(I) abbildet und die beide bzgl. des Akzeptanzverhaltens äquivalent sind. Das und nicht mehr sind die Anforderungen an eine Reduktion, google es gerne nach.
Ich brauche solche Details nicht zu Googeln, wenn ich es doch (anscheinend ebenso wie Du) studiert habe. Formal ist es natürlich eine Reduktion. Es ergibt aber abseits davon keinen Sinn und gerade weil der Fragesteller ein Laie ist, liegt darin eine Begründete Vermutung, dass Reduktionen nicht richtig erfasst wurden.
Genau solche Reduktionen verlangen wir auf unseren Übungsblättern, um das Verständnis zu verbessern, also so viel dazu...
Es liefert natürlich keine tieferenErkenntnisse zu den Problemen, da man dies nur legitimerweise tun kann, wenn man das Problem vorher schon löst, aber aus formaler Sicht ist es sinnvoll, um die Relation besser zu verstehen. Es ist in diesem Fall in P eben nicht relevant, ob man eine sinnvolle, nichttriviale Beziehung findet, und das merkt man so.
ich kann beispielsweise
https://www.youtube.com/watch?v=fkWcQBo3FgQ&list=PLG_1tsKrsKVNVbcjKJ_XnoQ1FKM2KeBj5&index=6
ziteren, wo dies auf 12:24 genau so erklärt wird. Die Vorgangsweise wird nachher bzw. im nächsten Video auch begründet. Mir ist klar dass diese Videos nur an der Oberfläche kratzen und ein Laienniveau bedienen, aber ich will mich ja auch nur als Laie etwas damit befassen, da ich es in einem anderen Zusammenhang benötige. Letztendlich war dies ja der Kern meiner Frage...
Ich will jetzt hier auch keine Likes oder Dislikes vergeben, da ich im Thema nicht mitzureden vermag.
Alles gut, das passt. Es ging ihm wohl darum, dass das Beispiel nicht gut verdeutlicht, wie Reduktionen im Allgemeinen durchgeführt werden. da das hier eher die Ausnahme (wenn auch eine relevante) ist. Das sollte sich aber erübrigen, wenn du dir mal allgemeinere Reduktionen anschaust, insbesondere zu NP-Schwere.
naja, hab ich das nicht gemacht? ich reduziere L2 auf L1 indem ich zuerst entscheide, ob z2=5729278907899900789000787777703565641 eine Primzahl ist und wenn ja, dann füttere ich L1 mit 2, ansonsten mit 3. Dass dies keinen praktischen Sinn ergibt ist klar, aber es ist wohl eine zulässige Polyzeitreduktion. Zumindest hab ich das so gelernt.
man kann sich ja vorstellen, dass man die Lösung des Problems in L2 als Teil der Funktion f(.) betrachtet. Auch deine Definition schließt dies ja nicht aus. Und f(.) ist dann auf jeden Fall in Polyzeit durchführbar, da ja auch L2 in Polyzeit ausführbar ist - oder?
Ich kann es nicht beurteilen, so hab ich es aber gelernt: es ist etwas "exotisch", aber dennoch eine Polyzeitreduktion . Ich habe oben Dogetastisch gebeten, dies zu beurteilen - ich kann es selbst nicht.
OK. Ich denke es wird erst interessant, wenn man NP betrachtet, aber diese Notation hat mich echt verwirrt: Die Relation <=p sagt also nichts über die Komplexität aus, sondern bloß, dass eine Reduktion möglich ist - das ist ja bei Problemen in P immer (wenn auch nicht "sinnvoll") möglich (siehe mein Beispiel). Hab ich das so nun richtig verstanden?