Eine Anthologie der Komplexitätsannahmen

32

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Σ2P P S A T [ k ]P S A T [ k + 1 ]PSEINT[k]=PSEINT[k+1]PSEINT[k]PSEINT[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:

  1. Yao hält die folgende Annahme für plausibel: .RPϵ>0DTichME(2nϵ)
  2. 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):

  1. Die Annahme selbst;
  2. Das erste Papier, in dem die Annahme gemacht wird;
  3. Interessante Ergebnisse, in denen die Annahme verwendet wird;
  4. 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:

  1. Wiki der kryptografischen Primitive und schwieriger Probleme in der Kryptografie .
  2. Helger Lipmaas kryptografische Annahmen und schwierige Probleme .
Sadeq Dousti
quelle
2
Nett. David Johnson hat etwas Ähnliches für Komplexitätsergebnisse getan, die verwendet wurden, um die Härte der Approximation in einer kürzlich erschienenen Spalte zu zeigen.
Suresh Venkat
@ Suresh: Ein Link zu Johnsons Kolumne wird sehr geschätzt.
MS Dousti
Das Anfordern des ersten Papiers kann schwierig sein.
András Salamon
@ András: Ja. Aus diesem Grund habe ich die Phrase "wann immer möglich" hinzugefügt. Sie können das Papier zitieren, das Sie für das erste halten. Da dies CW ist, korrigiert jeder, der ein älteres Ergebnis kennt, einfach den Beitrag.
MS Dousti

Antworten:

10
  • Annahme: Exponentielle Zeithypothese .
  • Zuerst zitiert in: Als Folklore wurde es zuerst in der folgenden Veröffentlichung formuliert: Russell Impagliazzo und Ramamohan Paturi. 1999. Die Komplexität von k-SAT . In Proceedings of the Fourth Annual IEEE Konferenz über Computational Complexity ( COCO '99 ). IEEE Computer Society, Washington, DC, USA, 237-240.
  • Verwendung (en): Es wird davon ausgegangen, dass kein NP-vollständiges Problem in subexponentieller Zeit entschieden werden kann, und dies impliziert daher, dass P ≠ NP ist.
  • Status: Offen.
Unglaublich
quelle
Die ETH geht davon aus, dass das 3-SAT-Problem nicht in subexponentieller Zeit entschieden werden kann. Antworten auf diesen Beitrag ( cstheory.stackexchange.com/questions/3620/… ) implizieren die Existenz subexponentieller Zeitalgorithmen für einige NP-vollständige Probleme wie Planar Independent Set.
Mohammad Al-Turkistany
Wie Mohammad schreibt, ist die Beschreibung in "Use (s)" ungenau oder einfach falsch.
Yoshio Okamoto
@YoshioOkamoto: Dies ist ein Community-Wiki-Beitrag. Warum nicht den Beitrag präzisieren oder sogar korrigieren?
MS Dousti
Ich bin mir nicht sicher. Die verlinkte Wikipedia-Seite enthält weitere Informationen, und meine Bearbeitung wäre nur eine Wiederholung.
Yoshio Okamoto
8
  • Annahme : NP hat kein p-Maß 0
  • Zuerst zitiert in : Jack H. Lutz. Kategorie und Maß in Komplexitätsklassen . SIAM J. Comput. 19: 1100-1131, 1990.
  • μp(NP)0PNP
    1. Tpmp
    2. Es gibt ein Paar nicht zusammenhängender Sprachen in NP, die P-untrennbar sind [4];
    3. α<1nα-ttp
    4. mp
    5. NP enthält eine P-Bi-Immunsprache [3];
    6. ENEEENEEEENEE

PNP

  • Status : Offen

[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.

Joshua Grochow
quelle
Ausgezeichnet. Ich glaube, Sie können die Annahme auf Lutz '1987er Dissertation " Ressourcengebundene Kategorie und Messung in Exponentialkomplexitätsklassen " oder auf seine 1987er IEEE-Arbeit "Ressourcengebundene Baire-Kategorie und kleine Schaltkreise im Exponentialraum" zurückführen (die online nicht verfügbar ist !).
MS Dousti
6
  • Annahme: NEEEE .
  • Zuerst zitiert in: Mihir Bellare und Shafi Goldwasser. 1994. Die Komplexität der Entscheidung versus Suche . SIAM J. Comput. 23, 1 (Februar 1994), 97-119.
  • Verwendung (en): Wenn die Annahme zutrifft, gibt es in NP Probleme, deren Suchversion nicht (polynomiell) auf ihre Entscheidungsversion reduziert wird. Mit anderen Worten, unter der gegebenen Annahme sind nicht alle Sprachen in NP selbstreduzierbar .
  • Status: Offen.
Sadeq Dousti
quelle