Was sind übliche Techniken, um Probleme miteinander zu reduzieren?

40

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.L1L2L2L1L1L2

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!

Raphael
quelle
Sehen Sie hier einige Gedanken auf der Suche nach geeigneten Partnern und Ideen für Kürzungen.
Raphael

Antworten:

18

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.L1RL2RL1L2

In der "Praxis" bekommen wir und stehen vor dem Problem, einen guten Reduktionspartner , dh einen Sonderfall von , der sich als erwiesen hat .L2L1L2R

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

f(A,k)=(A,(1,,1),k,|A|)

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)vVWw

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

3SAT ist ein Sonderfall; mit genügt die Anzahl der Sätze in .f(φ)=(φ,m)mφ

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

f(A)={(A,12aAa),aAamod2=0(A,1+aA|a|),else

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)Akk

Ü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 .Gs,tGkstGk

Zeigen Sie, dass LONGEST-PATH NP-hart ist.

HAMILTON-CYCLE ist ein bekanntes NP-vollständiges Problem und ein Spezialfall für LONGEST-PATH. für einen beliebigen Knoten in reicht aus. Beachten Sie insbesondere, dass das Reduzieren von HAMILTON-PATH mehr Arbeit erfordert.f(G)=(G,v,v,n)vG

Raphael
quelle
2
Hier ist ein Beispiel namens TPP (Travelling Purchaser Problem), dessen Spezialfall viele schwierige Probleme aufweist.
Juho
Ein weiteres Beispiel für die Berechenbarkeit ist das spezielle Halteproblem (das normalerweise direkt als unentscheidbar erwiesen ist), ein Sonderfall des allgemeinen Halteproblems.
Raphael
Ist KNAPSACK wirklich eine korrekte Reduktion von SUBSET-SUM? KNAPSACK fragt nach Wert und SUBSET-SUM fragt nach genauem Wert, nein? Zum Beispiel wäre eine SUBSET-SUM-Instanz eine 'no'-Instanz (ich kann nicht genau 4 von nur einem Element mit dem Wert 5 erhalten), aber Ihre KNAPSACK-Reduktion würde dies auf reduzieren und , also wäre es eine 'Ja'-Instanz ... Oder vermisse ich etwas? >=v{5},4{5},{1},4,15>4
Johnny
15

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

DOUBLE-SAT={φφ is a boolean formula with at least 2 satisfying assignments }

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

NP -Härte ergibt sich aus einer Reduktion von . Bei einer gegebenen Formel ändern wir sie, indem wir eine neue Variable . Wir fügen der Formel eine neue Klausel . Wenn nun erfüllbar ist, ist es sowohl mit als auch mit erfüllbar . Daher mindestens 2 erfüllenden Belegungen. Ist hingegen nicht erfüllbar, wird es unabhängig vom Wert von definitiv nicht erfüllbar .SATφv(v¬v)φv=⊥v=φφv

Daraus folgt , dass ist -komplette, das ist , was wir zeigen wollten.DOUBLE-SATNP

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.

Juho
quelle
6

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

MKfML

mit das Halteproblem (oder eine andere unentscheidbare Sprache / ein anderes Problem).K={MM(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:MfMfM

Dasselbe gilt für den Nachweis, dass nicht halbentscheidbar ist, indem nicht halbentscheidbare Sprachen als Reduktionspartner gewählt werden, z. B. :LK¯


  1. Hier kommt die Gödel-Nummerierung ins Spiel: Wir erhalten (in der Regel) kostenlos eine Berechenbarkeit dieses Mappings.
Raphael
quelle
-2

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).ABBA

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.

vzn
quelle
2
Ich frage mich, ob Sie die Fußnote in der Frage bemerkt haben. Ich denke, die Antworten sollten sehr spezifisch sein und zeigen, wie eine bestimmte Methode angewendet wird. Dies scheint ziemlich vage und allgemein. Wie wäre es, wenn Sie als Verbesserung zeigen, wie die Gadgets konstruiert und verwendet werden können?
Juho
2
Außerdem: Sie könnten erklären, warum und wie etwas von den beteiligten Komplexitätsklassen abhängt. Was mache ich dann , wenn ich von nach oder von nach gehen möchte? Was ist mit dem "nächstgelegenen Problem"? Können Sie ein Beispiel für ein Problempaar nennen? ABBA
Juho
Der Powerpoint zeigt zwei Beispiele für die Verwendung von Minianwendungen. ein Beispiel für ein nächstgelegenes Problem: Angenommen, man hat ein Problem im Zusammenhang mit der Zahlentheorie. Es gibt einen Abschnitt von G & J, der sich mit der Zahlentheorie befasst. und so weiter. Wie für andere Komplexitätsklassen außerhalb von NP gibt es viele, aber die Listen der Probleme sind nicht so gründlich oder leicht zu erhalten. Mit anderen Worten, um die ursprüngliche Frage einzugrenzen, sollte sie möglicherweise auf vollständige NP-Reduzierungen beschränkt sein ...?
VZN
2
Ich empfehle, der Antwort alle Informationen hinzuzufügen, da Kommentare jederzeit gelöscht werden können. Der Link zu den Folien könnte morgen ebenfalls unterbrochen werden. Was ich mit dem Problem in der Nähe erreicht habe: Was mache ich genau, wenn ich ein Problem finde, das ähnlich aussieht (vorausgesetzt, ich bin ein absoluter Anfänger)?
Juho