In der Arbeit The Random Oracle Hypothesis Is False diskutieren die Autoren (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan und Rohatgi) die Auswirkungen der Zufalls-Orakel-Hypothese . Sie argumentieren, dass wir nur sehr wenig über die Trennung von Komplexitätsklassen wissen und die meisten Ergebnisse entweder die Verwendung vernünftiger Annahmen oder die Zufalls-Orakel-Hypothese beinhalten. Die wichtigste und weit verbreitete Annahme ist, dass die PH nicht zusammenbricht. In ihren Worten:
In einem Ansatz nehmen wir als Arbeitshypothese an, dass PH unendlich viele Ebenen hat. Somit wird jede Annahme, die implizieren würde, dass PH endlich ist, als falsch angesehen. Zum Beispiel haben Karp und Lipton gezeigt, dass, wenn NP ⊆ P / poly ist, PH zu kollabiert . Wir glauben also, dass SAT keine polynomgroßen Schaltkreise hat. In ähnlicher Weise glauben wir, dass die Sätze Turing-complete und Many-one complete für NP nicht spärlich sind, da Mahaney gezeigt hat, dass diese Bedingungen zu einem PH-Kollaps führen würden. Man kann sogar zeigen, dass für jedes k ≥ 0 bedeutet, dass PH endlich ist. Daher glauben wir, dass P S A T [ k ] ≠ P S A T [ k + 1 ] für alle k ≥ 0. Wenn also die Polynomhierarchie tatsächlich unendlich ist, können wir viele Aspekte der rechnerischen Komplexität von NP beschreiben.
Abgesehen von der Annahme, dass die PH nicht zusammenbricht, gab es viele andere Komplexitätsannahmen. Zum Beispiel:
- Yao hält die folgende Annahme für plausibel: .
- Nisan und Wigderson machen verschiedene Annahmen im Zusammenhang mit der Derandomisierung.
Die Grundidee dieser Frage ist, was der Titel besagt: Eine Anthologie komplexitätstheoretischer Annahmen zu sein. Es wäre großartig, wenn die folgenden Konventionen eingehalten würden (wann immer möglich):
- Die Annahme selbst;
- Das erste Papier, in dem die Annahme gemacht wird;
- Interessante Ergebnisse, in denen die Annahme verwendet wird;
- Wenn die Annahme jemals widerlegt / bewiesen wurde oder ob ihre Plausibilität jemals diskutiert wurde.
This post is meant to be a community wiki; if an assumption is already cited, please edit the post and add new information rather than making a new post.
Bearbeiten (31.10.2011): Einige kryptografische Annahmen und Informationen dazu sind auf den folgenden Websites aufgeführt:
Antworten:
quelle
[1] J. Lutz und E. Mayordomo. Cook versus Karp / Levin: Vollständigkeitsbegriffe trennen, wenn NP nicht klein ist . Theoret. Comp. Sci. 164: 141 & ndash; 163, 1996.
[2] D. Juedez und J. Lutz. Die Komplexität und Verteilung schwerer Probleme . SIAM J. Comput 24 (2): 279 & ndash; 295, 1995.
[3] E. Mayordomo. Fast jeder Satz in exponentieller Zeit ist P-bi-immun . Theoret. Comp. Sci. 136: 487 & ndash; 506, 1994.
[4] L. Fortnow, J. Lutz und E. Mayordomo. Untrennbarkeit und starke Hypothesen für disjunkte NP-Paare . In Jean-Yves Marion und Thomas Schwentick, Herausgeber, Proceedings of the 27. Symposium on Theoretical Aspects of Computer Science, Band 5 von Leibniz International Proceedings in Informatics (LIPIcs), S. 395-404. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Deutschland, 2010.
quelle
quelle