Polytime-Algorithmus für SUBSET-SUM unter der Annahme von P = NP

7

Auf der Wikipedia-Seite zum P vs. NP-Problem gibt es einen Algorithmus, der SUBSET-SUM "löst", falls P = NP in Polynomzeit ist. (Es ist eine Idee, ein TM zu finden, das ein Zertifikat gibt). Aber es gibt "Ja" in Polynomzeit und läuft für immer, wenn die Antwort "Nein" ist. Es kann offensichtlich festgelegt werden, in exponentieller Zeit "nein" zu geben (nur um einen exponentiellen Algorithmus auszuführen, wenn der erste zu lange läuft).

Aber können wir explizit einen "ehrlichen" Algorithmus beschreiben, der SUBSET-SUM (oder ein anderes NP-vollständiges Problem) in Polynomzeit unter der Annahme von P = NP löst (und ich meine, wirklich löst)?

Mit "ehrlich" und "wirklich löst" meine ich, dass der Algorithmus die klassischen Definitionen für einen Polynom-Zeit-Algorithmus erfüllt, dh hier sollten Konstanten existieren so dass bei jeder Eingabe Algorithmus in nicht mehr als enden würde Schritte und geben "yes" aus, wenn SUBSET-SUM und andernfalls "no". Der Wikipedia-Algorithmus erfüllt die erste Bedingung nicht und löst das Problem daher nicht wirklich.C1,C2xC1|x|C2x

Thefacetakt
quelle
Ich glaube das ist unbekannt. Das Gebiet ist als optimale heuristische Algorithmen bekannt . Einer der Hauptforscher ist Edward A. Hirsch .
Yuval Filmus
@djechlin ist richtig und Wikipedia ist falsch: Der Algorithmus hält immer an, weil er schließlich auf eine Brute-Force-Methode trifft und das Problem löst. Da alle Programme miteinander verzahnt sind, kann auch die Laufzeit leicht analysiert werden: Wenn der te Algorithmus bei Eingabe in Schritten eine Antwort gibt , hat simuliert Schritte insgesamt, unabhängig von komplexitätstheoretischen Annahmen; Es ist wahr, unabhängig von der wahren Komplexität von SUBSET-SUM. Diese Suchmethode wird Levin Search genannt, manchmal Universal Search. WxatWΘ((a+t)2)
Lieuwe Vinkhuijzen

Antworten:

2

Ich kann das zur Hälfte beantworten, aber ich glaube, die tiefere Frage, die Sie sich stellen, ist etwas, das ich gerade lerne :)

Der Algorithmus auf Wikipedia, nennen wir es W, basiert auf der Idee: Anstatt Zertifikate zu erraten, warum nicht einfach den deterministischen P-Algorithmus D selbst erraten? Dies ist teuer, aber da es unabhängig von der Eingabe ist, ist es O (1) (falls ein solcher Algorithmus existiert). Der Algorithmus entscheidet tatsächlich immer, auch wenn P! = NP ist, da es natürlich eine Reihe von "Brute Force" -Programmen gibt, die nur ein mögliches Zertifikat ausdrucken und dann anhalten, sodass W auf eine sehr langsame Brute Force zurückgreifen kann.

Das Problem ist, dass Sie tatsächlich keine Möglichkeit haben, das an Sie zurückgegebene Programm zu überprüfen . Sie können sich vorstellen, W auszuführen und feststellen, dass es ein bestimmtes Programm zu bevorzugen scheint, aber Sie können feststellen, dass es bei größeren Eingaben schließlich einen Fehler in diesem Programm findet und weitergeht. Es scheint sich auf einen Algorithmus zu einigen, der zu sein scheint, aber später einen Fehler darin zu finden und zu einem -Algorithmus zu wechseln . Sie werden nie erfahren, wann es das "richtige" gefunden hat.n7n2000

Dies ist eigentlich die gleiche Idee, die im Beweis des Karp-Lipton-Theorems verwendet wurde: Wenn genügend Rechenleistung vorhanden ist, können Sie damit ganze Klassen von Programmen erraten und überprüfen, ob sie funktionieren (der Beweis lautet genau: "Errate ein Programm und" Vergewissern Sie sich, dass es funktioniert, und verwenden Sie es dann ", was ein wenig Rechenleistung erfordert - mehr als NP -, um erfolgreich zu sein.)

Mir ist keine Theorie darüber bekannt, wie kompliziert eine Lösung sein kann, aber vielleicht kann jemand, der besser informiert ist, antworten.

Das konkretere Szenario in der P = NP-Realität ist, dass jemand tatsächlich einen Algorithmus für jedes NP-vollständige Problem wie SAT erstellt.

Ich denke, Sie haben eine gute Frage gestellt, und ich bin gespannt, wie ich die Lücken in meiner Antwort schließen kann, wie W im Semi-Practice analysiert und nützlicher gemacht werden kann.

Djechlin
quelle
Gute Antwort! +1. Es gibt einen subtilen Unterschied zwischen dieser Suche und Karp-Lipton: Hier müssen wir nur die Lösung überprüfen, die das Programm bietet; Im Karp-Lipton-Theorem müssen Sie überprüfen, ob das Programm korrekt ist (für alle )x{0,1}
Lieuwe Vinkhuijzen
-1

Ich werde versuchen, Ihre Frage teilweise zu beantworten, aber ich denke, es sollte für Ihre Suche ausreichen.

NP-komplett zu sein, bedeutet NP UND NP-HARD zu sein.

NP-HARD zu sein bedeutet, dass jedes Problem in NP über eine polynomielle Zeittransformation in dieses Problem übersetzt werden kann.

SSP ist bekanntermaßen NP-HARD (und NP-COMPLETE).

Dies bedeutet zum Beispiel, dass Sie im Internet nach der spezifischen Polynom-Zeit-Transformation suchen können, die zeigt, dass SSP NP-HARD ist (auf jedem Papier, das dies beweist).

Diese Transformation ist ein "ehrlicher" Algorithmus, der garantiert in Polynomzeit ausgeführt wird und irgendwo in einem Papier geschrieben ist. Nennen wir es 'SSP-T' (für die SSP-Transformation).

Der einzige Weg, um zu beweisen, dass P = NP ist, besteht darin, einen Polynom-Zeit-Algorithmus für ein Problem in NP auszustellen.

Wenn Sie also annehmen, dass P = NP ist, nehmen Sie an, dass Sie in Ihren eigenen Händen einen "ehrlichen" Polynom-Zeit-Algorithmus zur Lösung eines (beliebigen) NP-Problems haben. Nennen wir diesen Algorithmus: 'H'

Nun ... angesichts eines Problems in NP nennen wir es "My-NP-Problem" ...

Die Lösung, die Sie suchen, ist:

  • Wenden Sie SSP-T an, um es in eine Instanz von SSP umzuwandeln.

  • Verwenden Sie nun erneut SSP-T, um diese SSP-Instanz in eine Instanz von 'H' umzuwandeln (das EINE - jedes - Problem NP, das Sie in P lösen können - basierend auf der Annahme, dass P = NP - ),

  • Führen Sie H aus, um eine Lösung zu finden.

  • Verwenden Sie SSP-T, um die Lösung unter SSP zu interpretieren

  • Verwenden Sie SSP-T noch einmal, um die Lösung unter 'My-NP-Problem' (das willkürliche Problem, das Sie am Anfang lösen wollten) zu interpretieren.

Und los geht's!

Diese 5 aufeinander folgenden Schritte sind der "ehrliche" Algorithmus, nach dem Sie gesucht haben.

Jeder Schritt läuft in Polynomzeit und wird durch die Definition jedes Konzepts garantiert existiert.

Sie hätten jedes andere NP-HARD-Problem anstelle von SSP wählen können, da die Definition von NP-HARD (per Definition!) Garantiert, dass:

  • SSP-T existiert,

  • ist ein Algorithmus,

  • ist bidirektional,

  • ist gültig und gilt für jedes NP-Problem; und

  • läuft in Polynom-Zeit

In der Tat, wenn Sie die üblichste Art und Weise zu zeigen, dass ein Problem NP-HARD ist, ist VIA eine Umwandlung in SAT-3, was eines der ersten Probleme war, das NP-HARD gezeigt wurde (irgendwann in den 60er / 70er Jahren).

Lassen Sie mich wissen, welche Schwächen Sie in den von mir gegebenen Überlegungen / Erklärungen finden könnten.

Martin Carames Abente
quelle
1
Es ist nicht wahr, dass der einzige Weg, um zu beweisen, dass P = NP ist, darin besteht, einen Polytime-Algorithmus für ein Problem in NP zu zeigen. Es reicht zu beweisen, dass ein solcher Algorithmus existiert. Außerdem sucht das OP nach einem konkreten Algorithmus, der derzeit beschrieben werden kann.
Yuval Filmus
Ich denke, Sie haben Recht, nur die Existenz eines solchen 'H' (eine Lösung in Polynomzeit für ein bestimmtes NP-Problem) würde zeigen, dass P = NP ist. Trotzdem
Martin Carames Abente
(Fortsetzung des letzten Kommentars) Trotzdem bleiben die 5 angegebenen Schritte ein tatsächlicher / konkreter Algorithmus, dessen Eingabe 'H' ist. Genau wie SSP-T als Eingabe hat: die Instanz eines NP-Problems (diejenige, die in eine Instanz oder SSP umgewandelt werden soll - oder umgekehrt -). "Führen Sie H aus, um eine Lösung zu finden" ist ein konkreter Schritt, wenn Sie H als Eingabe haben. Auf der anderen Seite YF, wenn OP eine konkrete Lösung erwartet, die auf einem Existenzsatz basiert, haben Sie Recht. Aber ich glaube nicht, dass er das erwartet. Es wäre ähnlich, eine konkrete Lösung von P = NP in Wikipedia zu erwarten.
Martin Carames Abente