Wie konstruiere ich Reduktionen zwischen Problemen, um zu beweisen, dass ein Problem NP-vollständig ist?

Ich absolviere einen Komplexitätskurs und habe Probleme, Reduzierungen zwischen NPC-Problemen zu finden. Wie kann ich Reduzierungen zwischen den Problemen finden? Gibt es einen allgemeinen Trick, den ich verwenden kann? Wie soll ich mich einem Problem nähern, bei dem ich beweisen muss, dass es sich um einen NPC handelt?

Es gibt keine magische Kugel; NP-Härteprüfungen sind hart. Für alle diese Beweise gibt es jedoch einen allgemeinen Rahmen. Viele Schüler, die mit NP-Härteprüfungen zu kämpfen haben, sind verwirrt darüber, was sie tun sollen, was es offensichtlich unmöglich macht, herauszufinden, wie es geht. Hier ist also, was zu tun ist, um ein NP-hartes Problem zu beweisen.

Erstens müssen Sie sich entscheiden, welches NP-schwierige Problem Sie auf Ihr Problem reduzieren möchten, es sei denn, Sie machen nur Hausaufgaben . Dies ist größtenteils eine Frage des "Geruchs". Wenn die Zahl 3 irgendwo in der Problembeschreibung erscheint, versuchen Sie, sie von oder 3 C o l o r oder . (Ja, ich meine es ernst.) Wenn Ihr Problem darin besteht, eine optimale oder Permutation oder einen optimalen Pfad zu finden, versuchen Sie es mit einer Reduzierung von oder . Wenn Sie nach der kleinsten Teilmenge mit einer bestimmten Eigenschaft , versuchen Sie es mit$\mathsf{3SAT}$$\mathsf{3Color}$$\mathsf{3Partition}$$\mathsf{HamiltonianCycle}$$\mathsf{HamiltonianPath}$$\mathsf{Clique}$; Wenn Sie nach der größten Teilmenge mit einer bestimmten Eigenschaft , versuchen Sie es mit . Wenn Ihr Problem damit zusammenhängt, etwas im Flugzeug zu tun, versuchen Sie es mit oder . Und so weiter. Wenn Ihr Problem nicht nach irgendetwas "riecht", ist oder wahrscheinlich die beste .P l a n a r C i r c u i t S A T P l a n ein r T S P 3 S A T C i r c u i t S A $\mathsf{IndependentSet}$$\mathsf{PlanarCircuitSAT}$$\mathsf{PlanarTSP}$$\mathsf{3SAT}$$\mathsf{CircuitSAT}$

Natürlich müssen Sie bereits genau wissen , wie all diese Probleme definiert sind , und je einfacher das Problem ist, von dem aus Sie es reduzieren, desto besser. So kühl wie das Ergebnis am Ende aussehen könnte, empfehle ich nicht von der Reduzierung $\mathsf{Minesweeper}$ oder $\mathsf{Tetris}$ oder $\mathsf{OneCheckersMove}$ oder $\mathsf{SuperMarioBros}$ .

Zweitens die tatsächliche Reduzierung. Um das Problem X (von dem Sie wissen, dass es NP-schwer ist) auf das Problem Y (von dem Sie beweisen möchten, dass es NP-schwer ist) zu reduzieren, müssen Sie einen Algorithmus beschreiben, der eine beliebige Instanz von X in eine legale Instanz von Y umwandelt Der Verkleinerungsalgorithmus muss für jedes "Feature" der X-Instanz etwas Spezifisches tun, der Teil der Ausgabe für jedes "Feature" wird normalerweise als Gadget bezeichnet .

Aber was ist ein Feature? Das hängt von Problem X ab. Zum Beispiel:

• Um eine Instanz von zu transformieren , benötigen Sie ein Gadget für jede Variable und für jede Klausel in der Eingabeformel. Jedes variable Gadget sollte zwei "Zustände" haben, die "wahr" und "falsch" entsprechen. Jedes Klausel-Gadget sollte auch mehrere "Zustände" haben, von denen jeder mindestens eines der Literale in dieser Klausel als wahr erzwingt. (Die Zustände sind nicht Teil der Ausgabe des Reduktionsalgorithmus.)$\mathsf{3SAT}$

• Um eine Instanz von zu transformieren , benötigen Sie ein Gadget für jeden Scheitelpunkt und jede Kante des Eingabediagramms sowie ein weiteres Gadget zum Definieren der drei Farben.$\mathsf{3Color}$

• $\mathsf{PlanarCircuitSat}$

Die tatsächliche Form des Gadgets ist abhängig von Problem Y, der einen Sie reduzieren zu . Wenn Sie sich beispielsweise auf ein Problem mit Diagrammen beschränken, handelt es sich bei Ihren Minianwendungen um kleine Untergraphen. Siehe den Wikipedia-Artikel. Wenn Sie sich auf ein Planungsproblem beschränken, besteht jedes Gadget aus einer Reihe von zu planenden Jobs. Wenn Sie sich auf ein Problem mit Mario beschränken , besteht jedes Gadget aus Blöcken, Steinen und Koopas.

Dies kann verwirrend werden, wenn beide Probleme dieselbe Art von Objekt betreffen. Wenn beispielsweise sowohl X als auch Y Probleme mit Diagrammen darstellen, transformiert Ihr Algorithmus ein Diagramm (eine Instanz von X) in ein anderes Diagramm (eine Instanz von Y). Wählen Sie Ihre Notation mit Bedacht aus, damit Sie diese beiden Diagramme nicht verwechseln. Ich empfehle auch dringend, mehrere Tintenfarben zu verwenden.

Schließlich muss Ihr Reduktionsalgorithmus drei Eigenschaften erfüllen:

• Es läuft in Polynomialzeit. (Dies ist normalerweise einfach.)

• Wenn Ihrem Reduktionsalgorithmus eine positive Instanz von X als Eingabe zugewiesen wird, wird eine positive Instanz von Y als Ausgabe erstellt.

• Wenn Ihr Reduktionsalgorithmus eine positive Instanz von Y als Ausgabe erzeugt, muss ihm eine positive Instanz von X als Eingabe gegeben worden sein.

Hier gibt es eine wichtige Subtilität. Ihr Verkleinerungsalgorithmus funktioniert nur in einer Richtung, von X zu Y. Um jedoch zu beweisen, dass der Algorithmus korrekt ist, müssen Sie über die Transformation in beide Richtungen nachdenken. Sie müssen auch bedenken, dass Ihr Reduktionsalgorithmus nicht erkennen kann , ob eine gegebene Instanz von X positiv oder negativ ist - das würde die Lösung eines NP-harten Problems in Polynomzeit erfordern!

Das ist was . Das kommt wie eben mit üben.

JeffE umreißt die gängigste Strategie: Kennen Sie viele NP-vollständige Probleme, finden Sie eine, die sehr gut passt, und vereinfachen Sie die Reduzierung.

Eine andere gültige Strategie besteht darin, immer 3SAT (oder ein anderes Problem) zu verwenden. Dies könnte einige Reduzierungen komplizierter machen, aber der Vorteil ist, dass Sie viel Erfahrung darin haben, die Zufriedenheit bei anderen Arten von Problemen zum Ausdruck zu bringen. So sparen Sie sich die Zeit, einen guten Reduktionspartner zu finden (einschließlich Sackgassen), und hoffen, dass Ihre Erfahrung es Ihnen ermöglicht, die Reduktion schnell durchzuführen, auch wenn es schwieriger ist.

Auch dieser Ansatz hat eine gewisse Schönheit: (3) SAT ist eines der wenigen Probleme, für die die NP-Vollständigkeit (fast) direkt nachgewiesen wurde. Wenn Sie sich daher nur auf diesen Beweis verlassen, bleibt Ihr "Beweisbaum" flach, und es werden keine langen Reduktionsketten erzeugt.