Auf der Suche nach Literaturquelle für folgende Idee

12

Ich bin mir ziemlich sicher, dass ich nicht der erste bin, der die Idee aufgreift, die ich präsentieren werde. Es wäre jedoch hilfreich, wenn ich Literatur zu dieser Idee finden könnte.

Die Idee ist, eine Turing-Maschine M mit der Eigenschaft zu konstruieren, dass wenn P = NP, dann M 3-SAT in der Polynomzeit auflöst. (Die Wahl von 3-SAT ist willkürlich. Es könnte wirklich jedes Problem in NP sein).

Nur um klar zu sein, ist dies keine Behauptung, dass P = NP ist. Tatsächlich glaube ich das Gegenteil. Ich sage nur, wenn P = NP, dann liefert M eine Lösung in Polynomzeit. Wenn Sie nach einer effizienten Lösung suchen, sollte ich Sie warnen, dass dies alles andere als effizient ist.

M ist wie folgt aufgebaut: Nehmen Sie zunächst eine kanonische Codierung für alle Turing-Maschinen an und weisen Sie diesen Maschinen eine Nummerierung zu. Es gibt also eine Turing-Maschine mit der Nummer 1, eine mit der Nummer 2 usw. Die Idee einer Universal-Turing-Maschine, die das Format für eine bereitgestellte Maschine liest und dann simuliert, dass diese Maschine auf einer separaten Eingabe läuft, ist ziemlich bekannt. M wird eine Universal Turing Machine einsetzen, um jede Turing Machine nacheinander zu konstruieren und zu simulieren.

Es simuliert zunächst den Betrieb von Turing Machine 1 für einen einzelnen Schritt.
Anschließend wird die Ausgabe von Turing Machine 1 betrachtet. Anschließend wird
der Ablauf von Turing Machine 1 in zwei Schritten simuliert und die Ausgabe überprüft. Anschließend wird Turing Machine 2 in zwei Schritten simuliert. Es fährt fort und schleift auf diese Weise, indem es Turing Machine 1 für k Schritte, dann 2 für k Schritte ... und schließlich Machine k für k Schritte ausführt.

Nach jedem Simulationslauf wird die Ausgabe des Laufs untersucht. Wenn die Ausgabe eine Zuweisung von Variablen ist, die die 3-SAT-Probleminstanz erfüllen, wird M in einem Akzeptanzzustand angehalten. Wenn andererseits die Ausgabe eine Proofzeichenfolge in einer überprüfbaren Proofsprache ist, mit dem nachgewiesenen Ergebnis, dass die Probleminstanz nicht befriedigend ist, wird M in einem Ablehnungszustand angehalten. (Als Beweissprache könnten wir zum Beispiel die Peano-Axiome mit Logik zweiter Ordnung und die grundlegenden logischen Axiome nach Hilbert verwenden. Ich überlasse es dem Leser als Übung, herauszufinden, ob P = NP gilt Proof-Sprache existiert und ist zur Polynomzeit überprüfbar).

Ich werde hier behaupten, dass M 3-SAT in der Polynomzeit genau dann löst, wenn P = NP ist. Irgendwann wird der Algorithmus eine magische Turing-Maschine mit der Nummer K finden, die zufällig ein effizienter Löser für das 3-SAT-Problem ist und in der Lage ist, die Ergebnisse für Erfolg oder Misserfolg nachzuweisen. K wird schließlich simuliert, indem für ein Polynom poly (strlen (input)) Schritte ausgeführt werden. Das Polynom für M ist ungefähr das Quadrat des Polynoms für k im größten Faktor, aber mit einigen schrecklichen Konstanten im Polynom.

Um hier meine Frage zu wiederholen: Ich möchte wissen, ob es eine Literaturquelle gibt, die diese Idee verwendet. Ich bin etwas weniger daran interessiert, die Idee selbst zu diskutieren.

Provinz Bill
quelle

Antworten:

16

Es scheint, dass diese Idee Levin zugeschrieben wird (es wird optimale Suche genannt). Ich glaube, dass diese Tatsache bekannt ist. Ein ähnlicher Algorithmus wird beispielsweise in Wikipedia beschrieben , obwohl das Teilmengen-Summenproblem verwendet wird. In diesem Artikel von scholarpedia finden Sie mehrere Referenzen zu diesem Thema, einschließlich eines Zeigers auf den ursprünglichen Algorithmus und auf einige andere optimale Suchalgorithmen.

φP=NPφ

Kommentar 2: Wie Jaroslaw Blasiok in einer anderen Antwort hervorhob, entscheidet dieser Algorithmus Sat nicht nur unter der Annahme von P = NP.

Mateus de Oliveira Oliveira
quelle
Ich habe gerade die Wikipedia-Referenz gefunden, und zwar erwähnt sie Levin, aber ohne zu zitieren. Es könnte sein, dass dies einfach zur Folklore geworden ist, aber in der veröffentlichten Literatur nie verwendet wurde. Unabhängig davon ist dies hilfreich. Vielen Dank.
Bill Province
Herzlich willkommen. Ich habe eine Homepage mit mehreren Referenzen zu diesem Thema gefunden. Ich habe die Antwort bearbeitet, um sie einzuschließen.
Mateus de Oliveira Oliveira
6

Die Idee, alle möglichen Turing-Maschinen diagonal laufen zu lassen, wurde zuvor von Leonid Levin in der Levins Universal Search verwendet. Leider und entgegen dem weit verbreiteten Missverständnis können meines Wissens Variationen der universellen Levins-Suche KEINEN expliziten Algorithmus liefern, der SAT (Entscheidungsproblem) in Polynomzeit löst, vorausgesetzt, dass P = NP - und Ihr Algorithmus auch nicht .

Die Einschränkung der vorgeschlagenen Argumentation liegt (wie so oft) in der "einfachen Übung, die dem Leser überlassen wurde" - ich konnte die Übung nicht selbst beweisen und glaube nicht, dass ihre Aussage wahr ist, nämlich:

Unter der Annahme von P = NP gibt es ZFC-Polynomgrößen, die beweisen, dass eine gegebene Boolesche Formel nicht erfüllt werden kann.

Übrigens: Ich kann nicht nachweisen, wie die Existenz eines polynomiell kurzen ZFC unter der (stärkeren) Annahme, dass "P = NP in ZFC nachweisbar ist" als Beweis für die Unzufriedenheit angesehen werden kann. Es wird jedoch unter noch stärkeren Voraussetzungen einfach, nämlich:

(*) Es gibt Maschine M, die in Polynomzeit läuft und SAT nachweislich löst.

Und dies ist, glaube ich, die richtige Annahme, unter der Ihr Algorithmus SAT in Polynomialzeit löst. Oben mit "löst SAT nachweislich" meine ich: Es gibt eine Maschine M und einen ZFC-Beweis, dass M SAT löst.

Beachten Sie, dass diese Annahme noch etwas schwächer ist als die folgende: (**) Es gibt eine Maschine M, die nachweislich in Polynomzeit läuft und nachweislich SAT löst.

Unter (**) kann man eine explizite Konstruktion haben, die dasselbe Ziel erreicht, was noch einfacher ist: Zählen Sie alle ZFC-Beweise auf, bis Sie die richtige Maschine M finden (die konstante Zeit verbringt), und führen Sie dann M für eine bestimmte Instanz aus.

Es ist jedoch wahr, dass unter der Annahme von P = NP ein polynomisch verifizierbares Beweissystem mit kurzen Beweisen für die Unbefriedigbarkeit einer gegebenen Formel existiert. Leider kennen wir weder das Proofsystem noch den Prüfer aus der Hand und es ist in dieser Einstellung nicht hilfreich.

f-1(x)

Beachten Sie, dass dieses Schema beispielsweise für das FACTORING-Problem gilt. Hier ist f nur Multiplikation (definiert nur für andere Faktoren als \ pm 1) und B ist Primaritätsprüfung. Daher wäre Levins universelle Suche (bis auf einen konstanten Faktor) ein optimaler Algorithmus für FACTORING. Vorausgesetzt, der optimale Algorithmus ist langsamer als der bekannte Algorithmus für die Primaritätsprüfung - im anderen Fall wird die Primaritätsprüfung dominant.

Darüber hinaus kann mit der Levins - Methode unter der Annahme P = NP ein expliziter Algorithmus zur Lösung eines Entscheidungsproblems in bereitgestellt werden NPcÖ-NP

Jarosław Błasiok
quelle
1
Wenn P = NP, dann ist co-NP = co-P = P = NP. UNZUFÜLLIGKEIT ist also in NP, ebenso Zeugen in Polynomgröße - Sie müssen keine Turing-Maschine aufrufen. Können Sie diesen Zeugen nicht in einen ZFC-Beweis umwandeln, dass die Formel nicht befriedigend ist? Ich bin nicht mit der Mechanik des ZFC-Beweises vertraut, aber die Intuition, die ich von verschiedenen Stellen erhalten habe, ist, dass ZFC allen Dingen entspricht, von denen Sie dachten, Sie könnten sie sowieso schon beweisen Sie haben von Mengenlehre gehört. Endliche Objekte wie eine Boolesche Formel und ein polynomischer Zeuge für ihre Unbefriedigbarkeit sind wahrscheinlich nicht sonderbar.
David Richerby
Ja, wenn P = NP, dann ist UNSAT in NP, und es hat Zeugen der Polynomgröße. Nämlich: Zeugen ohne Größe, die ganze Arbeit wird vom Prüfer erledigt, oder? Ich habe nur eine Idee, wie ich diesen Zeugen mit der Größe Null in ZFC umwandeln kann, um Unzufriedenheit zu beweisen: Geben Sie einen ZFC-Beweis, dass mein Computer UNSAT tatsächlich löst, und zeigen Sie dann einen Durchlauf dieses Computers nach der Formel - das wäre ein gültiger Beweis. und dies entspricht der Tatsache, dass der von OP vorgeschlagene Algorithmus unter (*) arbeitet. Aber was wäre, wenn es eine knifflige Maschine gäbe, die SAT einfach lösen könnte, aber diese Tatsache ist nicht beweisbar? Nicht, dass ich es für richtig halte
Jarosław Błasiok
1
Das Missverständnis, auf das ich mich beziehe, ist: "Wenn P = NP, dann gibt Levins Universal Search einen polynomiellen Zeitalgorithmus zur Lösung des NP-vollständigen Problems" oder wie es manchmal heißt: "Es ist unmöglich, nur einen nichtkonstruktiven Beweis für P = NP zu haben, weil of Levins Algorithmus ". Beide sind falsch - die Wikipedia-Formulierung präsentiert eine Methode, die bei YES-Instanzen von SUBSET SUM in polytime stoppt, bei NO-Instanzen jedoch überhaupt nicht stoppt - es ist kein Algorithmus, der über die Teilmengensumme in polytime entscheidet. Die OP-Formulierung ist für diesen Zweck besser, erfordert jedoch eine stärkere Annahme als P = NP, um SAT in polytime zu bestimmen.
Jarosław Błasiok
1
NPcÖ-NP
1
Der Weg, um damit umzugehen, besteht, wie Sie nicht explizit wissen, ob ein unSAT-Problem vorliegt, darin, einen kurzen Beweis in einer formalen Logik zu finden, die wir bereits kennen und die wir überprüfen können (seien es ZFC-Axiome oder Peano - wir sind es) eher ein kurzer Beweis in der ersteren zu finden), dass diese Instanz nicht befriedigend ist. Wenn man aber beweisen will, dass es in dieser formalen Logik einen so kurzen Beweis gibt, braucht man eine stärkere Annahme als P = NP.
Jarosław Błasiok