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

2 Antworten

Vom Beitragsersteller als hilfreich ausgezeichnet

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.


YBCO123 
Beitragsersteller
 23.08.2022, 13:51

da habe ich dann zu viel reininterpretiert.

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.


YBCO123 
Beitragsersteller
 23.08.2022, 07:24

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.

YBCO123 
Beitragsersteller
 23.08.2022, 07:18

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  23.08.2022, 14:08
@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.