Auszüge aus dem Buch.

22

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!

Neeldhara
quelle
1
Community-Wiki.
Dave Clarke
@supercooldave: Danke - das hätte ich wohl beim Posten tun sollen. Mein Versehen!
Neeldhara
@Jukka: Danke! Ich dachte, das hat Supercooldaves Edit getan. Mir ist jetzt klar, dass Edit ein Tag hinzugefügt hat. Es ist jetzt ein CW :)
Neeldhara
8
Vielleicht sollte das Plakat klarstellen, was mit "aus dem Buch" gemeint ist. Ich hätte gedacht, dass (in Analogie zu den Beweisen aus dem Buch) alle Algorithmen aus dem Buch kurz, einfach zu formulieren, elegant und fast magisch funktionieren. Der andere Thread hat jedoch viele Posts mit wahnsinnig komplexen Algorithmen, die keine der von mir genannten Eigenschaften erfüllen.
Robin Kothari
3
@Robin: Wahrnehmungen unterscheiden sich. Ich fand keinen der Beweise von "Proofs from THE BOOK" einfach (na ja, fast keinen). Und bereits der zweite Beweis (Bertrands Postulat) erfordert mehrere Seiten, so dass sie auch nicht zu kurz sind. - Umgekehrt finde ich viele der Algorithmen im verwandten Thread recht einfach (im Nachhinein natürlich), und es ist nicht zu leugnen, dass sie kurz sind.
Konrad Rudolph

Antworten:

9

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.

Noam
quelle
Eine Erklärung für diese Reduzierung (wenn ich mich nicht irre) finden Sie auf Seite 7 von "Nachweisbare Sicherheit von Kryptosystemen: Eine Übersicht". Hier ist ein Link: cs.yale.edu/publications/techreports/tr288.pdf
Neeldhara
9

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.

Lev Reyzin
quelle
2
Vielen Dank! Das erscheint mir sehr vielversprechend und auch völlig neu. Ich sollte etwas Zeit mit diesem Tutorial und den anderen Referenzen verbringen.
Neeldhara
8

Koch-Levin-Theorem

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

Rui Ferreira
quelle
8

Ganzzahlmultiplikation zu schnellen Fourier-Transformationen!

Jeffε
quelle
6
und die Konsequenz: String Matching zu FFTs!
Suresh Venkat
6

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.

Michaël Cadilhac
quelle
1
Noch schöner ist die Verallgemeinerung von Rice-Shapiro. Siehe Cutlands Ausstellung: books.google.com/… )
Diego de Estrada
3

SAT zu 3SAT

kk>3

Rui Ferreira
quelle
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 .

Rui Ferreira
quelle
1
Die Reduktion mit NAESAT anstelle von 3SAT (in Papadimitrious Buch) ist direkter.
Diego de Estrada
3

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

Reduzieren der Sortierung auf ein konvexes Rumpfproblem.

user200
quelle
2

GENAUE ABDECKUNG DURCH 3-SÄTZE-ZUSAMMENFASSUNG

U={1,2,,3m}S1,,SnUmU

w1,,wnKK

Si{0,1}3mn+1Siwi=jSi(n+1)3mjK=j=03m1(n+1)j

(Meine Quelle war Papadimitrious Buch.)

Diego de Estrada
quelle