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.
quelle
Antworten:
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.n7 n2000
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.
quelle
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.
quelle