Die "Direktionalität" von Reduktionen?

Ich war etwas verwirrt mit der Richtung der Reduzierungen, die verwendet wurden, um zu zeigen, dass bestimmte Sprachen nicht rekursiv sind. wir zum Beispiel an, wir möchten feststellen, ob das ( ) unentscheidbar ist. Ich weiß, wir können davon ausgehen, dass es entscheidbar ist, und dann versuchen, einen Entscheider für das Akzeptanzproblem zu bauen, was unmöglich ist. Obwohl wir das Akzeptanzproblem ( ) verwenden, um die Entscheidbarkeit des Halteproblems zu lösen, haben wir das Akzeptanzproblem auf das Halteproblem reduziert, nicht umgekehrt, oder? $HALT_{TM}$ $A_{TM}$

Ich bin manchmal etwas verwirrt, wenn ich auf Fragen stoße, die mich auffordern, eine Reduzierung durchzuführen. Ich werde gebeten, die Sprache auf zu reduzieren , aber was das bedeutet, ist, dass eine einfachere Instanz eines Problems von , richtig (oder sollte es zumindest sein)? Ich gehe davon aus, dass es unmöglich ist, eine einfachere Version eines Problems auf eine komplexere Version eines Problems zu reduzieren. Habe ich Recht, wenn ich das glaube? $x$ $y$ $y$ $x$

computability turing-machines reductions halting-problem Chris T.
quelle

Wenn wir glauben, dass es schwierig ist, eine Leiter zum Mond zu bauen, müssen wir auch glauben, dass es mindestens genauso schwierig ist, ein Gerät zu bauen, das ein Objekt dupliziert - denn wenn ein solches Gerät einfach zu bauen wäre, könnten wir eine setzen Befestigen Sie die resultierenden zwei Leitern, um eine Leiter mit doppelter Höhe zu erhalten, und wiederholen Sie diesen Vorgang einige Male, um das von uns angenommene Problem leicht zu lösen. Hier habe ich das Problem des Aufbaus einer Mondleiter auf das Problem des Aufbaus eines Objektduplikators reduziert, um zu zeigen, dass der letztere mindestens so schwer ist wie der erstere.

j_random_hacker

@j_random_hacker Diese Analogie scheint ziemlich verworren zu sein und scheint schnell zusammenzubrechen. Ich könnte einfach eine normale Leiterfabrik benutzen, um meine Leitern zu bekommen (ein Kopierer ist also nicht erforderlich), und nachdem ich ein paar Leitern zusammengeklebt habe, wird die gesamte Konstruktion so schwach sein, dass sie unter ihrem eigenen Gewicht zusammenbricht (also a Duplikator ist nicht ausreichend).

David Richerby

@ DavidRicherby: Zugegeben, die strukturellen Überlegungen sind ein großes Problem, kein Argument :) Wenn man diese jedoch ignoriert, ist die Tatsache, dass eine Leiterfabrik ausreicht, kein Problem: Problem A zu zeigen ist mindestens so schwer wie Problem B, es reicht aus, es zu zeigen Alle Instanzen von B können gelöst werden, indem in Instanzen von A transformiert wird, und somit löst das Lösen von A auch B; Die Existenz anderer Lösungen für B ist irrelevant. (In der Tat bedeutet die Tatsache, dass ein Objektduplizierer verwendet werden kann, um eine Leiterfabrik zu implementieren, dass das Problem des "Vervielfältigers" mindestens so schwer ist wie das Problem der "Leiterfabrik", was eine gültige Schlussfolgerung zu sein scheint!)

psmears

Mögliches Duplikat von Wenn Problem A auf Problem B reduziert wird, welches Problem ist komplexer?

Kevin

@ DavidRicherby: Durch das Schreiben von "to the moon" habe ich wohl auf den fadenscheinigsten Teil der Analogie aufmerksam gemacht (nämlich die Fadenscheinigkeit der Leitern). Und ohne Raum, um "hart" zu definieren, wollte ich eine Technik, die "eine lineare Menge an Arbeit" oder schlechter (wie Ihre Leiterfabrik) benötigt, um als "hart" und "eine logarithmische Menge an Arbeit" (wie mein Kopierer) zu qualifizieren qualifizieren sich als "einfach". Vielleicht funktioniert diese Analogie nicht, aber ich denke, eine etwas genaue, etwas realistische Analogie sollte möglich und hilfreich sein.

j_random_hacker

Antworten:

Keine Sorge - alle sind verwirrt über die Richtung der Ermäßigungen. Sogar Leute, die seit Jahrzehnten mit Algorithmen und Komplexität arbeiten, haben gelegentlich die Frage: "Warten Sie, sollten wir auf oder auf reduzieren ?" Moment. $A$ $B$ $B$ $A$

Das Reduzieren von auf ergibt eine Aussage der Form "Wenn ich lösen könnte , würde ich auch wissen, wie man löst ". "Lösen" in diesem Sinne könnte "Berechnen mit einer beliebigen Turing-Maschine" oder "Berechnen in Polynomzeit" oder einen anderen Lösungsbegriff bedeuten, den Ihr Kontext erfordert. $A$ $B$ $B$ $A$

Dies mag nicht intuitiv erscheinen, da " reduziert sich auf " impliziert, dass das Lösen von mindestens so schwierig ist wie das Lösen von , sodass Sie die Schwierigkeit nicht reduziert haben. Sie können sich jedoch vorstellen, dass Sie weniger Probleme lösen müssen. Stellen Sie sich vor, Sie wollten zu Beginn des Tages einen Algorithmus für und einen Algorithmus für . Nun, da Sie eine Reduzierung von auf , haben Sie Ihre Ziele darauf reduziert, nur einen Algorithmus für . $A$ $B$ $B$ $A$ $A$ $B$ $A$ $B$ $B$

David Richerby
quelle

"Wenn ich B lösen könnte, dann würde ich auch wissen, wie man A löst." "- Wenn Sie wissen, dass das Lösen von A schwierig ist, dann wissen Sie auch, dass das Lösen von B mindestens genauso schwierig ist.

G. Bach

Ein Physiker und ein Mathematiker wurden jeweils gebeten, zwei Nägel zu entfernen, von denen einer bis zum Anschlag in die Wand geschlagen war, der andere nur zur Hälfte. Der Physiker zog zuerst den heraus, der sich auf halber Strecke befand, und schaffte es dann nach einiger Zeit, den zweiten herauszuziehen. Der Mathematiker begann mit dem, der sich ganz in der Wand befand, da er interessanter war. Nach einiger Zeit und Mühe gelang es ihm, es herauszuholen. Dann sah er den anderen an und sprach die Worte aus: "Dies kann zu einem bereits gelösten Fall vereinfacht werden." Er schlug ihn ganz in die Wand.

Wildcard

Nein. Wenn auf reduziert wird , bedeutet dies intuitiv, dass einfacher als und nicht umgekehrt. $A$ $B$ $A$ $B$

Praktischer: Nehmen Sie an, Sie möchten überprüfen . Anstatt dies auf irgendeine Weise zu tun, transformieren Sie gemäß einer (Reduktions-) Funktion . Sie müssen jetzt einchecken . $x \in A$ $x$ $y=f(x)$ $y \in B$

Sie haben noch nicht gelöst , das Ausgangsproblem , da jetzt bleiben Sie mit einem anderen Problem zu lösen: . Dies bedeutet, dass Sie das ursprüngliche Problem auf ein anderes reduziert haben . $x \in A$ $y \in B$

Es mag zunächst kontraintuitiv erscheinen, dass wir einfache Dinge auf komplexere reduzieren. In der Tat, pragmatisch, warum sollte man eine einfache Aufgabe lösen wollen, um sich auf eine schwierigere Aufgabe zu reduzieren ? Möchten wir unsere Aufgabe nicht stattdessen auf eine noch einfachere Aufgabe reduzieren?

Die Wahrheit ist jedoch: Wenn wir eine schwierige Aufgabe lösen könnten, indem wir sie auf eine einfache Aufgabe reduzieren , bedeutet dies, dass nicht wirklich schwieriger als . Wenn das Lösen von durch Anwenden der Reduktionsfunktion und anschließendes Lösen des "leichteren" erreicht werden kann, bedeutet dies in der Tat, dass in erster Linie einfacher als . $A$ $B$ $A$ $B$ $A$ $B$ $A$ $B$

Chi
quelle

Eine Reduktion von zu ist etwas , das Teil der Arbeit erledigt tun musste und was bleibt zu tun ist . Zum Beispiel kann "Essen bekommen" durch "Zutaten holen" auf "Kochen" reduziert werden. Dies bedeutet, dass "Kochen" schwieriger ist als "Essen bekommen": Jeder, der "kochen" kann, kann "Essen bekommen" (vorausgesetzt, die Reduzierung "Zutaten bekommen" funktioniert immer, zum Beispiel in Gegenwart eines Ortes, an dem Zutaten kostenlos angeboten werden) . $A$ $B$ $A$ $B$

Das Zeichnen von Dingen erleichtert das Verständnis:

Sie möchten die blaue Box erstellen (die einen Algorithmus darstellt, der eine Eingabe und entscheidet, ob ). Die Reduzierung ist dann die rote Box, und sobald Sie sie haben, müssen Sie nur noch die grüne Box bauen, um die blaue Box zu bauen. Wenn Sie also eine rote Box haben (die auf reduziert ), bauen Sie die grüne Box (die entscheidet $x$ $x\in A$ $A$ $B$ $B$ ) ist mindestens so schwer wie das Bauen des blauen (das entscheidet $A$ ): Wenn Sie eine grüne Box haben, ist es sehr einfach, eine blaue zu bauen. Wenn Sie eine blaue Box bauen, können Sie möglicherweise keine grüne Box bauen.

Beachten Sie, dass die Gründe für die beiden Bedingungen, die eine Reduzierung definieren, in dieser Zeichnung aufgeführt sind: die Tatsache, dass $f$ ist berechenbar bedeutet, dass Sie die rote Box bauen können, während die Tatsache, dass $f(x)\in B\iff x \in A$ bedeutet, dass Sie die beiden Drähte ganz rechts verbinden können.

xavierm02
quelle

Ich finde den ersten Absatz ziemlich schwer zu befolgen (ich bin mir auch nicht sicher, ob die Analogie sehr aufschlussreich ist), aber für den Rest der Antwort eine eindeutige +1.

David Richerby