Gründe zu glauben, dass

27

Es scheint, dass viele Leute glauben, dass , auch weil sie glauben, dass Factoring nicht polyzeitlösbar ist. (Shiva Kintali hat hier einige andere Kandidatenprobleme aufgelistet ).PNPcoNP

Andererseits haben Grötschel, Lovász und Schrijver geschrieben, dass "viele Leute glauben, dass ". Dieses Zitat ist in Geometrische Algorithmen und Kombinatorische Optimierung zu finden, und Schrijver macht ähnliche Aussagen in Kombinatorische Optimierung: Polyeder und Effizienz . Dieses Bild verdeutlicht, wo Jack Edmonds zu diesem Thema steht.P=NPcONP

Welche Beweise stützen einen Glauben an ? Oder um ?P = N P c o N PPNPcONPP=NPcONP

Austin Buchanan
quelle
Definieren Sie "Grund". Es gibt wirklich keine Beweise auf die eine oder andere Weise. Dies kann nicht experimentell getestet werden. Bis wir einen Beweis auf die eine oder andere Weise haben, sind es die einzigen "Gründe zu glauben" , entweder dass ein Problem in nicht polynomisch ist, oder irgendein , dass sie alle sind. NPcoNP
Jmite
2
Ich hatte auf Antworten gehofft, wie sie Scott Aaronson für P versus NP gegeben hatte .
Austin Buchanan
1
Viele der gleichen Aaron-Ideen sind anwendbar. stimme nicht mit jmite überein. es gibt viele Indizien Beweise, einschließlich der experimentellen Beweise, einige wie von Aaronson aufgeführt.
vzn
5
Satz 3.1 von Einwegpermutationen und selbstzeugenden Sprachen C. Homan und M. Thakur, Zeitschrift für Computer- und Systemwissenschaften, 67 (3): 608-622, November 2003. [ as .pdf ] besagt, dass P ∩ UP∩ coUP genau dann, wenn ("worst case") Einweg-Permutationen existieren. Satz 3.2 erinnert an 10 weitere Hypothesen, die sich als äquivalent zu P ≠ UP∩coUP erwiesen haben.
Thomas Klimpel
9
Ich denke, Factoring ∈ P ist um viele, viele Größenordnungen wahrscheinlicher als P = NP ∩ coNP, und das ist sicher nicht der Grund, warum ich P = NP ∩ coNP glaube.
Peter Shor

Antworten:

5

Satz 3.1 von Einwegpermutationen und selbstzeugenden Sprachen C. Homan und M. Thakur, Zeitschrift für Computer- und Systemwissenschaften, 67 (3): 608-622, November 2003. [ as .pdf ] besagt, dass genau dann, wenn ("Worst-Case") Einweg-Permutationen existieren. Theorem 3.2 erinnert 10 weitere Hypothesen , die äquivalent gezeigt worden sein , um P U P c o U P .PUPcoUPPUPcoUP

Auch wir haben guten Grund zu vermuten , dass . Daher glauben die obige Satz und der Vermutung führen zu einem starken Grund , dass P N P c o N P .UPNPPNPcoNP


Haftungsausschluss: Ich habe die Bearbeitung meiner Antwort von Mohammad Al-Turkistany auf diese Community-Wiki-Antwort verschoben. Er glaubt, dass es die Frage perfekt beantwortet, da die Existenz von Einweg-Permutationen weithin angenommen wird. Ich selbst habe den Unterschied zwischen "Worst-Case" - und "Average-Case" -Einwegfunktionen noch nicht ausreichend verstanden, um zu behaupten, dass sie die Frage wirklich beantworten.

Thomas Klimpel
quelle
0

Ich glaube, dass es sehr platzsparende Zufallszahlengeneratoren von hoher Qualität gibt. Trotz dieser Überzeugung verwende ich normalerweise Mersenne Twister in meinem Code, der von hoher Qualität ist, aber nicht sehr platzsparend. Es gibt eine fehlende Verbindung zwischen Raumfahrteffizienz und NP∩coNP. Es ist nur ein Bauchgefühl, dass es eine Verbindung gibt.


Lassen Sie mich einen Grund nennen, warum ich glaube, dass "echte Zufälligkeit" sehr effizient simuliert / angenähert werden kann. Wir wissen, dass es möglich ist, Pseudozufallszahlen zu erzeugen, die für alle praktischen Zwecke (einschließlich Kryptographie) ausreichend zufällig sind. Wir wissen auch, dass die Verwendung (einer kleinen Menge fester) großer Primzahlen bei der Konstruktion von Pseudozufallszahlengeneratoren selten eine schlechte Idee ist. Aus Vermutungen wie Riemanns wissen wir, dass fast alle Primzahlen einen hohen Grad an Zufälligkeit enthalten, aber wir wissen auch, dass wir dies noch nicht konsequent beweisen können.

Gibt es eine intuitive Erklärung, warum sich die Primzahlen wie Zufallszahlen verhalten? Die Primzahlen sind das Komplement der zusammengesetzten Zahlen. Die Ergänzung eines wohlerzogenen Sets ist oft komplizierter als das ursprüngliche Set. Die zusammengesetzten Zahlen setzen sich aus Primzahlen zusammen, was dieser Menge wiederum bereits eine gewisse Komplexität verleiht.


Hintergrund Ich habe einmal versucht zu verstehen, warum P ≠ NP schwierig ist. Ich habe mich gefragt, ob die Approximation innerer Symmetriegruppen einer Probleminstanz durch nichtpotente Gruppen möglicherweise nicht zu einem "Abstraktionsalgorithmus" führt, der in der Lage ist, in die innere Struktur der Probleminstanz zu sehen. Aber dann wurde mir klar, dass selbst die Berechnung der Struktur einer nicht potenziellen Gruppe Factoring als Sonderfall beinhaltet. Die Frage der einfachen Untergruppen einer zyklischen Gruppe der Ordnung n ist gleichbedeutend mit der Bestimmung der Primfaktoren von n. Und die Klassifikation endlicher nichtpotenter Gruppenenthält noch schlimmere Unterprobleme im Zusammenhang mit der Isomorphie von Graphen. Das war genug, um mich davon zu überzeugen, dass dieser Ansatz nicht helfen wird. Aber mein nächster Schritt war zu verstehen, warum Factoring schwierig ist, und die obige Antwort ist, was ich mir ausgedacht habe. Es hat gereicht, um mich zu überzeugen, vielleicht wird es auch für andere Menschen überzeugend sein. (Ich wusste damals nichts über Gruppoide oder inverse Halbgruppen, die wahrscheinlich besser geeignet sind als nullpotente Gruppen für den Umgang mit inneren Symmetrien. Dennoch bleibt das Argument, warum ein solcher Ansatz nicht effizient sein wird, dasselbe.)

Thomas Klimpel
quelle
2
Ich bin nicht sicher, wie sich diese Antwort auf die Frage bezieht. Könnten Sie näher darauf eingehen?
Matthias
@Matthias Die Antwort ist der Grund, warum ich glaube, dass P ≠ NP≠coNP. Das Problem liegt also wahrscheinlich nicht in der Beziehung zur Frage, sondern in der Erklärung der Argumentation. Es handelt sich um eine Form des mathematischen Platonismus, die davon ausgeht, dass mathematische Strukturen nahezu alles modellieren oder approximieren können, was auf dieser Welt existieren kann. Echte Zufälligkeit ist ein Teil dessen, was existieren kann, und die Antwort versucht zu erklären, warum das Bauchgefühl besteht, dass diese Zufälligkeit bereits in hinreichend räumlich begrenzten Kontexten vorliegt, um P ≠ NP≠coNP zu verursachen. (Sorry, vielleicht werde ich diesen Kommentar später verbessern / entfernen.)
Thomas Klimpel
2
@Matthias Ich schrieb in der Antwort "... fehlende Verbindung zwischen Raumeffizienz und NP∩coNP, es ist nur ein Bauchgefühl ...". Ich könnte es versuchen, aber ich fürchte, das wird nicht gut aufgenommen. Ich denke, Sie möchten eher unabhängige Referenzen, die in diese Richtung zeigen, als meine eigenen Erklärungen. Im Complexity Zoo fand ich heraus, dass das angegebene Ergebnis "Worst-case" -Einweg-Permutationen nur dann vorliegen, wenn P nicht UP ∩ coUP [ HT03 ] entspricht. Die Zeitung ist online, aber ich habe sie (noch) nicht gelesen ...
Thomas Klimpel