In der Berechenbarkeits- und Komplexitätstheorie (und vielleicht auch in anderen Bereichen) sind Reduktionen allgegenwärtig. Es gibt viele Arten, aber das Prinzip bleibt dasselbe: Zeigen Sie, dass ein Problem mindestens so schwer ist wie ein anderes Problem indem Sie Instanzen von auf Instanzen in . Im Wesentlichen zeigen wir, dass jeder Löser für auch lösen wenn wir ihm erlauben, die Reduktionsfunktion als Präprozessor zu verwenden.
Ich habe im Laufe der Jahre meinen Anteil an Kürzungen vorgenommen, und etwas nervt mich immer wieder. Während jede neue Reduktion eine (mehr oder weniger) kreative Konstruktion erfordert, kann sich die Aufgabe wiederholen. Gibt es einen Pool kanonischer Methoden?
Welche Techniken, Muster und Tricks kann man regelmäßig anwenden, um Reduktionsfunktionen zu konstruieren?
Dies soll eine Referenzfrage werden . Achten Sie daher darauf, allgemeine, didaktisch aufbereitete Antworten zu geben, die an mindestens einem Beispiel illustriert sind, aber dennoch viele Situationen abdecken. Vielen Dank!
Antworten:
Der Sonderfall
Angenommen, wir wollen in Bezug auf einen Begriff der Reduktion . Wenn ein Sonderfall von ist, ist das ziemlich trivial: Wir können im Wesentlichen die Identitätsfunktion verwenden. Die Intuition dahinter ist klar: Der allgemeine Fall ist mindestens so schwer wie der Sonderfall.L1≤RL2 R L1 L2
In der "Praxis" bekommen wir und stehen vor dem Problem, einen guten Reduktionspartner , dh einen Sonderfall von , der sich als erwiesen hat .L2 L1 L2 R
Einfaches Beispiel
Angenommen, wir möchten zeigen, dass KNAPSACK NP-hart ist. Zum Glück wissen wir, dass SUBSET-SUM NP-vollständig ist und es sich in der Tat um einen Sonderfall von KNAPSACK handelt. Die Reduzierung
genügt; ist die KNAPSACK-Instanz, die fragt, ob wir mit Item-Werten in mindestens den Wert erreichen können, so dass die entsprechenden Gewichte von insgesamt unter bleiben . Wir brauchen keine Gewichtsbeschränkungen für die Simulation von SUBSET-SUM, also setzen wir sie einfach auf tautologische Werte.(V,W,v,w) v V W w
Einfaches Übungsproblem
Betrachten Sie das MAX-3SAT-Problem: Entscheiden Sie anhand einer Satzformel und einer Ganzzahl , ob es eine Interpretation von , die mindestens Klauseln erfüllt . Zeigen Sie, dass es NP-schwer ist.φ k φ k
Beispiel
Angenommen, wir untersuchen das SUBSET-SUM-Problem und möchten zeigen, dass es NP-schwer ist.
Wir haben Glück und wissen, dass das PARTITION-Problem NP-vollständig ist. Wir bestätigen, dass es sich in der Tat um einen Sonderfall von SUBSET-SUM handelt und formulieren
Dabei ist die Eingabemenge von PARTITION, und ist eine Instanz für SUBSET-SUM, die nach einer Teilmenge von , die zu summiert , fragt . Hier müssen wir uns darum kümmern, dass es kein passendes ; In diesem Fall geben wir ein beliebiges undurchführbares Beispiel an.A (A,k) A k k
Übungsproblem
Betrachten Sie das Problem LONGEST-PATH: Wenn ein gerichteter Graph , Knoten von und eine ganze Zahl , entscheiden Sie, ob es einen einfachen Pfad von nach in einer Länge von mindestens .G s,t G k s t G k
Zeigen Sie, dass LONGEST-PATH NP-hart ist.
quelle
Nutzung eines bekannten Problems in der Nähe
Wenn Sie mit einem Problem konfrontiert werden, das sich schwierig anfühlt, ist es oft eine gute Idee, nach einem ähnlichen Problem zu suchen, das sich bereits als schwierig erwiesen hat. Oder Sie können sofort erkennen, dass ein Problem einem bekannten Problem sehr ähnlich ist.
Beispiel Problem
Betrachten Sie ein Problem
Wir möchten zeigen, dass vollständig ist. Wir stellen schnell fest, dass es einem Problem sehr nahe kommt, von dem wir bereits wissen, dass es schwierig ist, nämlich dem Erfüllbarkeitsproblem (SAT) .NP
Die Zugehörigkeit zu ist einfach zu zeigen. Das Zertifikat besteht aus zwei Aufgaben. Es ist klar, dass in polynomialer Zeit überprüft werden kann, ob die Zuweisungen einer Formel entsprechen.NP
Daraus folgt , dass ist -komplette, das ist , was wir zeigen wollten.DOUBLE-SAT NP
Probleme in der Nähe finden
Probleme zu reduzieren ist eine Art Kunst, und Erfahrung und Einfallsreichtum sind oft erforderlich. Zum Glück sind bereits viele schwierige Probleme bekannt . Garey und Johnsons Computer und Intraktabilität: Ein Leitfaden zur Theorie der NP-Vollständigkeit ist ein Klassiker, dessen Anhang viele Probleme auflistet. Google Scholar ist auch ein Freund.
quelle
In Bezug auf die Berechenbarkeit untersuchen wir häufig Sätze von Turing-Maschinen. Das heißt, unsere Objekte sind Funktionen und wir haben Zugriff auf eine Gödel-Nummerierung . Das ist großartig, weil wir mit der Eingabefunktion so ziemlich alles machen können, was wir wollen, solange wir berechenbar bleiben.
Angenommen, wir wollen zeigen, dass nicht entscheidbar ist. Unser Ziel ist es, zur Äquivalenz des Schicksals zu gelangenL
mit das Halteproblem (oder eine andere unentscheidbare Sprache / ein anderes Problem).K={⟨M⟩∣M(⟨M⟩) halts}
Wir müssen also ein berechenbares Mapping , damit immer berechenbar ist. Dies ist ein kreativer Akt, der von der Gleichwertigkeit des Untergangs geprägt ist. Sehen Sie sich einige Beispiele an, um eine Vorstellung davon zu bekommen, wie dies funktioniert:⟨M⟩↦⟨fM⟩ fM
Dasselbe gilt für den Nachweis, dass nicht halbentscheidbar ist, indem nicht halbentscheidbare Sprachen als Reduktionspartner gewählt werden, z. B. :L K¯¯¯¯¯
quelle
es hängt von den beteiligten Komplexitätsklassen ab, und ob man von einem gegebenen zu einem unbekannten oder von einem unbekannten zu einem gegebenen reduzieren möchte . Das übliche Szenario ist, Probleme mit NP Hard oder NP Complete zu beweisen. Eine gebräuchliche Technik besteht darin, "Gadgets" in einer Domäne zu konstruieren, die sich auf eine bestimmte Weise verhalten und das Verhalten einer anderen Domäne imitieren. Um beispielsweise SAT in Vertex Cover umzuwandeln, werden "Gadgets" in Vertex Cover konstruiert, die sich ähnlich wie SAT-Klauseln verhalten, z. B. in der folgenden Diashow: NP Complete Reductions von Krishnamoorthy (auch mit einem Beispiel für Hamilton Path).A B B A
Eine nützliche Strategie besteht darin, aus einer großen Zusammenstellung von Problemen der betreffenden Komplexitätsklasse die "scheinbar nächstgelegenen Probleme" für das zu untersuchende Problem zu finden. Eine hervorragende Referenz in diesem Sinne sind Computer und Intractability, ein Leitfaden zur Theorie der NP-Vollständigkeit, Garey und Johnson, die nach verschiedenen Problemtypen organisiert sind.
quelle