Auszüge aus dem Buch.

Dies ist in Anlehnung an " Algorithmen aus dem Buch ". Obwohl Reduktionen auch Algorithmen sind, hielt ich es für zweifelhaft, dass man sich eine Reduktion der Antwort auf die Frage nach Algorithmen aus dem Buch vorstellen würde. Daher eine separate Abfrage!

Ermäßigungen aller Art sind herzlich willkommen.

Ich beginne mit der wirklich einfachen Reduktion von Vertex Cover auf Multicut on Stars. Die Reduzierung bietet sich fast an, sobald das Quellproblem identifiziert ist (davor würde ich kaum glauben, dass das Problem für die Sterne schwer sein würde). Diese Reduktion beinhaltet die Konstruktion eines Sterns mit Blättern und die Zuordnung eines Paares von Anschlüssen zu jeder Kante in der Grafik, und es ist "leicht zu sehen", dass es funktioniert. Ich werde dies mit einem Link zu einer Referenz aktualisieren, sobald ich eine gefunden habe.$n$

Diejenigen, denen der Kontext des Buches fehlt, sollten sich die Frage nach den Algorithmen aus dem Buch ansehen .

Update: Mir ist klar, dass mir nicht ganz klar war, was als Reduktion aus dem Buch zu qualifizieren ist. Ich finde dieses Problem ein bisschen knifflig, also gebe ich zu, dass ich dem Problem halb absichtlich ausgewichen bin, indem ich einen Verweis auf den anderen Thread eingefügt habe :)

Also lassen Sie mich beschreiben, was ich vorhatte, und ich nehme an, dass es selbstverständlich ist - YMMV in dieser Hinsicht. Ich beabsichtige eine direkte Analogie zu der ursprünglichen Absicht von Proofs aus dem Buch. Ich habe Reduktionen gesehen, die schrecklich klug sind, und habe mich darüber aufgeklärt, wie diese Abfolge von Gedanken bei jedem vorgekommen sein könnte. Während solche Reduzierungen mir ein Gefühl der Ehrfurcht geben, sind dies nicht die Beispiele, die ich in diesem Zusammenhang sammeln möchte.

Was ich suche, sind Reduzierungen, die ohne allzu große Schwierigkeiten beschrieben werden und vielleicht ein wenig überraschend sind, weil sie leicht zu erfassen, aber nicht leicht zu finden sind. Wenn Sie davon ausgehen, dass für die Reduzierung ein Vortrag erforderlich ist, dann passt das wahrscheinlich nicht in die Rechnung, obwohl ich mir sicher bin, dass es Ausnahmen gibt, in denen die hochrangige Idee elegant ist und der Teufel im Detail steckt (für die Ich bin mir nicht sicher, ob mir einer einfällt.

Das Beispiel, das ich gegeben habe, war absichtlich einfach und hoffentlich ein wenig - wenn nicht perfekt - illustrativ für diese Eigenschaften. Das erste Mal hörte ich über Multi-Schnitt in einem Klassenzimmer war, und unser Lehrer begann damit , dass nicht nur ist es NP-schwer im Allgemeinen, es ist NP-schwer , auch wenn sie auf Bäume beschränkt ... {dramatische Pause} der Höhe eins . Ich erinnere mich, dass ich es nicht sofort nachweisen konnte, obwohl es im Nachhinein offensichtlich erscheint.

Ich nehme an , dass es im Nachhinein naheliegend ist, genau zu beschreiben, wonach ich suche. Ich bin mir nicht sicher, ob dies etwas mit der Komplexität der Beschreibung zu tun hat - vielleicht gibt es Situationen, in denen etwas anscheinend Trübes als elegant eingestuft werden könnte -, aber ich würde mich über eine Begründung sehr freuen. Angesichts der Tatsache, dass dies irgendwann eine Geschmackssache ist, sollten Sie sich auf jeden Fall frei fühlen, das zu finden, was ich für wahnsinnig komplex und wunderschön halte. Ich freue mich auf eine Vielzahl von Beispielen!

Rabin zeigt die Einwegigkeit von (x ^ 2 mod N = pq) ohne die Faktorisierung von N durch eine Reduktion, die zeigt, dass man N faktorisieren kann, wenn man das Quadratwurzelmodul N = pq nehmen kann.

Beim maschinellen Lernen gibt es viele interessante Reduzierungen. Hier sind einige Beispiele:

• Multiklassifikation zu Binärklassifikation ( Link ) - man kann ein Problem der Auswahl unter vielen Klassen lösen, indem man einfachere Probleme der Auswahl zwischen zwei löst.
• Starkes Lernen zu schwachem Lernen ( Boosten ) - man kann willkürlich niedrige Fehlerraten erzielen, vorausgesetzt man kann etwas besseres als zufälliges erreichen.
• Ranking zur Klassifizierung ( Link )
• Quadratischer Verlust bei der Klassifizierung ( Sondierung ) - Man kann die Wahrscheinlichkeiten der Klassenzugehörigkeit schätzen, indem man einen Klassifikator mit einer kleinen Fehlerrate verwendet.

Ein Tutorial von Alina Beygelzimer, John Langford und Bianca Zadrozny behandelt einige andere.

Koch-Levin-Theorem

Jedes Problem in NP kann in der Polyzeit durch eine deterministische Umformmaschine auf SAT reduziert werden. Referenz siehe 1 .

Ganzzahlmultiplikation zu schnellen Fourier-Transformationen!

Reis-Theorem

Eines meiner liebsten. Es reduziert das Problem des Anhaltens auf eine beliebige Indexmenge (oder deren Ergänzung). Siehe zum Beispiel Sipser, Problem 5.28.

SAT zu 3SAT

$k$$k \gt 3$

3SAT bis 3COL

Verwenden von Gadgets, um 3SAT auf das Problem zu reduzieren, zu entscheiden, ob ein Diagramm mit 3 Farben färbbar ist. Referenz siehe 1 .

Im Sinne von - oh das war einfach - im Nachhinein:

Reduzieren der Sortierung auf ein konvexes Rumpfproblem.

GENAUE ABDECKUNG DURCH 3-SÄTZE-ZUSAMMENFASSUNG

$U=\{1,2,\ldots,3m\}$$S_1,\ldots,S_n$$U$$m$$U$

$w_1,\ldots,w_n$$K$$K$

$S_i$$\{0,1\}^{3m}$$n+1$$S_i$$w_i=\sum_{j\in S_i} (n+1)^{3m-j}$$K=\sum_{j=0}^{3m-1} (n+1)^j$

(Meine Quelle war Papadimitrious Buch.)