Warum lässt sich jedes Problem in P auf jedes andere Problem in P reduzieren und was heißt das?

Ich habe gerade gelernt, dass man jedes Entscheidungsproblem L1 über Σ in P auf jedes andere Problem L2 über Σ aus P reduzieren kann. Mit hat es hier "die Kette rausgehauen":

Eine Reduktion ist ja eine berechenbare Abbildung

$f:\ \Sigma\ \rightarrow\Sigma\$ $w\ ∈\ L_{1\ }\Longleftrightarrow\ f\left(w\right)\ ∈\ L_{1\ }$

jetzt könnte ich festlegen Σ = Natürliche Zahlen von 1 bis 1 Million

L1 = {w ∈ Σ | w ist prim)

L2 = {w ∈ Σ | w ist gerade)

und definieren:

f(w) = 6 wenn w prim

f(w) = 7 wenn w nicht prim

Dies erfüllt genau die obige Definition einer Reduktion.

Nur welchen Sinn macht es, hier von einer "Reduktion" zu sprechen, denn ich habe ja den Primtest auf eine Zahl nicht auf den Test auf Geradheit einer Zahl zurückgeführt.

Ich hätte intuitiv etwas als Reduktion bezeichnet, wenn ich durch die Entscheidung L2 auch L1 entscheiden kann. Hier liegt aber aus meiner Laiensicht ein "fauler Zauber" vor, denn in der Abbildungsvorschrift f ist eigentlich schon enthalten, dass ich dafür schon die Entscheidung auf Prim durchführen, also L1 lösen muss. Es "hört sich aber so an", als könnte man nun einen Primtest (der ja, obwohl in P liegend, relativ komplex ist) auf etwas "reduzieren", wo man nur auf Geradheit prüft (was ja von der Komplexität nicht vergleichbar ist). Jedenfalls ist das nicht im Sinne der Erfindung eines "funktionierenden" Algorithmus für L1, den ich zu lösen vermag, indem ich L2 löse.

Ich hoffe, ich habe mich in meiner Notation verständlich ausgedrückt und man weiß, was ich meine...(bin kein Informatiker, daher bitte Milde walten lassen ;-)

Habe ich eine falsche Vorstellung von einer Reduktion oder ist das einfach so?

Answer 1

[MagicalGrill]

Die Intuition von Reduktion:

• Wir wollen Problem L1 lösen
• Wir können Problem L2 lösen
• Wir haben einen Algorithmus f, der alle Worte aus L1 nach L2 abbildet und alle Worte außerhalb von L1 nicht nach L2.
• Wir können jetzt L1 lösen, indem wir w auf f(w) abbilden und prüfen, ob das Ergebnis in L2 liegt.

Mehr steckt nicht dahinter. Wir führen das Problem L1 auf L2 zurück unter der Verwendung von f. Im Algorithmus könnte das so aussehen:

public bool L2(Word w){
  // some code
  // returns true iff w is in L2
}

public Word f(Word w){
  // some code
  // returns a word in L2 iff w is in L1
}

public bool L1(Word w){
  return L2(f(w));
}

Typischerweise steckt der Großteil der Komplexität in der Funktion L2 drin, sodass das f tatsächlich "nur" eine Reduktion ist, wie du sie dir vorstellst. Aber das muss per Definition nicht so sein, wie man in deinem Beispiel sieht:

public bool isEven(int number){
  return number % 2 == 0;
}

public int f(int number){
  // some code
  // returns an even number iff parameter is prime
}

public bool isPrime(int number){
  return isEven(f(number));
}

Unter der Voraussetzung, dass f existiert, können wir PRIME unter Zuhilfenahme von EVEN lösen.

Es stimmt, dass wir damit die eigentliche Komplexität nach f verschoben haben. Aber dass das so einfach geht, liegt eben daran, dass PRIME ein P-Problem ist. Dementsprechend hast du Recht: Die Aussage, dass sich alle nicht-trivialen P-Probleme aufeinander reduzieren lassen, ist trivialerweise wahr und nichts weltbewegendes.

Comments

[YBCO123]

da habe ich dann zu viel reininterpretiert.

Answer 2

[KarlRanseierIII]

Ich versuche das zunächst mal abseits derInformatik zu erklären. Wir nehmen mal ein Problem:

Eindrehen einer Kreuzschlitzschraube. Dafür nehme ich den geeigneten Schraubendreher, der löst mir das Problem.

Nun habe ich eine Schlitzschraube und möchte die eindrehen -> Schlitzschraubendreher.

Eine Reduktion wäre quasi:

Ich habe einen Adapter, in den ich den Kreuzschlitz hinten reinstecke und der vorne einen Antrieb für Schlitzschrauben hat. Ich spare mir den Schlitzschraubendreher.

Das ist die Grundidee der Reduktion.

Du hast jetzt nichts anderes gemacht, als den Kreuzschlitz hinten in den Schlitzschraubendreher zu stecken und beide fest zu verbunden. Du kurbelst an Deinem Kreuzschlitz, drehst damit die Schlitzschraube ein, hast aber eigentlich nichts gewonnen, weil Du eh den Schlitzschraubendreher hast. (Hääää?)

------

Deine 'Nebenbedingung' der Funktion (wenn prim) ist ja nichts anderes als die Lösung des Entscheidungsproblemes selbst - natürlich kannst Du aus einer TM, die ein Problem entscheidet auch eine transformierende machen. Insofern, um zu wissen, daß L1 und L2 in P sind, muß ich ja bereits TMs besitzen, die das entscheiden oder reduzieren können, anders hätte ich ja nicht zeigen können, daß in PTIME entscheidbar. Insofern ist die Erkenntnis der Reduzierbarkeit (in PTIME) zwischen zwei Entscheidungsproblemen in P in gewisser Weise banal.

Das Hauptinteresse bei Reduktionen L1<=L2 ist eigentlich, daß man L2 entscheiden kann und jetzt eine transformierende TM konstruiert, die L1 auf L2 reduziert, sodaß man L1 nicht mehr direkt entscheiden muß, vor allem unter der Prämisse, daß die Transformation entsprechend einfacher ist.

Konkretes einfaches Beispiel

L1 w ist gerade, L2 w ist ungerade. Ich habe eine Turingmaschine Tu, die entscheiden kann, ob w ungerade ist. Ich baue mir eine transformierende TM T, sodaß T(w)=w+1. Wenn ich also nun wissen will , ob w gerade ist, muß ich mir keine TM Tg bauen, die L1 entscheidet, vielmehr, werfe ich T w hin, T addiert 1 drauf und danach entscheidet die TM Tu.. Ich habe "ist gerade" auf "ist ungerade" reduziert.

Comments

[YBCO123]

Dein einfaches Beispiel macht - im Gegensatz zu meinem Beispiel insofern Sinn, als ich es in der Praxis verwenden könnte, um L1 zu lösen, indem ich L2 in der Schublade habe und statt L1 eben dieses löse. Die Addition +1 inkludiert ja nicht bereits die Lösung von L1.

Ist meine angegebene "Reduktion" dennoch eine zulässige, oder hab ich da einen Denkfehler drin? Falls es tatsächlich eine "Reduktion" darstellt, dann erkenne ich nicht den "praktischen" Nutzen, die mir diese bringt und vor allem auch nicht den Mehrwert des dadurch ableitbaren Satzes "Jedes Problem in PTIME kann auf ein beliebiges anderes Probleme in PTIME reduziert werden." Das klingt zunächst aufregend, ist aber für mich, so wie es bewiesen wird, eine Aussage ohne Substanz. Sorry für meine laienhafte Herangehensweise...

[KarlRanseierIII]

@YBCO123

Nein, ich denke Deine Herangehensweise eine entscheidende TM ind eine transformierende zu konvertieren ist ok.

Letztlich ist die Erkenntnis der wechselseitigen Reduzierbarkeit, wenn man bereits die Zuordnung zu P kennt, banal - wie ich sagte. Es ist eine 'offensichtliche' Konsequenz

Komplexität ist extrem negativ, es geht eher darum zu erkennen, daß etwas nciht geht/sich nicht lohnt.

-----

Der "Umkehrschluß" ist doch: Kann ich zeigen, daß eine transformierende TM nicht konstruierbar ist, dann kann ich L1 nicht in PTIME entscheiden. Wenn ich doch eh weiß, daß beide in P liegen, dann sind sie eben ähnlich schwer und ineinander überführbar - wobei es da ja noch die P-Vollständigkeit gibt.

[YBCO123]

als ich las "Jedes Problem in PTIME kann auf ein beliebiges anderes Probleme in PTIME reduziert werden." dachte ich zuerst "wow, das geht echt? Wahnsinn, wie gibt es denn das? Irre!", aber als ich den "Beweis" kennenlernte, empfand ich das aber als völlige Mogelpackung...deshalb hab ich diese Frage gestellt.