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 ).
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.
Welche Beweise stützen einen Glauben an ? Oder um ?P = N P ∩ c o N P
cc.complexity-theory
np
conditional-results
Austin Buchanan
quelle
quelle
Antworten:
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 .P≠UP∩coUP P≠UP∩coUP
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 .UP≠NP P≠NP∩coNP
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.
quelle
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.)
quelle