Une anthologie des hypothèses de complexité

32

Dans l'article The Random Oracle Hypothesis Is False , les auteurs (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan et Rohatgi) discutent des implications de l' hypothèse de l'oracle aléatoire . Ils soutiennent que nous savons très peu de choses sur les séparations entre les classes de complexité, et la plupart des résultats impliquent soit l'utilisation d' hypothèses raisonnables , soit l'hypothèse d'oracle aléatoire. L'hypothèse la plus importante et la plus répandue est que le PH ne s'effondre pas. Dans leurs mots:

Dans une approche, nous supposons comme hypothèse de travail que PH a une infinité de niveaux. Ainsi, toute hypothèse qui impliquerait que PH est fini est considérée comme incorrecte. Par exemple, Karp et Lipton ont montré que si NP ⊆ P / poly, alors PH s'effondre en Σ2P . Donc, nous pensons que SAT n'a pas de circuits de taille polynomiale. De même, nous pensons que les ensembles complets de Turing et plusieurs ensembles complets pour NP ne sont pas rares, car Mahaney a montré que ces conditions s'effondreraient PH. On peut même montrer que pour tout k ≥ 0, implique que PH est fini. Par conséquent, nous pensons quePSAT[k]=PSAT[k+1]PSAT[k]PSAT[k+1] pour tout k ≥ 0. Ainsi, si la hiérarchie polynomiale est bien infinie, nous pouvons décrire de nombreux aspects de la complexité de calcul de NP.

Outre l'hypothèse selon laquelle le PH ne s'effondre pas, il existe de nombreuses autres hypothèses de complexité. Par exemple:

  1. Yao considère que l'hypothèse suivante est plausible: .RPϵ>0DTIME(2nϵ)
  2. Nisan et Wigderson émettent plusieurs hypothèses liées à la dérandomisation.

L'idée principale de cette question est ce que dit son titre: être une anthologie des hypothèses théoriques de complexité. Ce serait formidable si les conventions suivantes étaient respectées (dans la mesure du possible):

  1. L'hypothèse elle-même;
  2. Le premier document dans lequel l'hypothèse est faite;
  3. Résultats intéressants dans lesquels l'hypothèse est utilisée;
  4. Si l'hypothèse a déjà été réfutée / prouvée, ou si sa plausibilité a déjà été discutée.

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.


Modifier (31/10/2011): Certaines hypothèses cryptographiques et informations à leur sujet sont répertoriées dans les sites Web suivants:

  1. Wiki des primitives cryptographiques et des problèmes difficiles en cryptographie .
  2. Hypothèses cryptographiques et problèmes difficiles d' Helger Lipmaa .
Sadeq Dousti
la source
2
Agréable. David Johnson a fait quelque chose de similaire pour les résultats de complexité utilisés pour montrer la dureté de l'approximation dans une colonne récente.
Suresh Venkat
@Suresh: Un lien vers la colonne de Johnson est très apprécié.
MS Dousti
Exiger le premier papier peut être délicat.
András Salamon
@ András: Oui. Pour cette raison, j'ai ajouté l'expression "chaque fois que possible". Vous pouvez citer le document que vous pensez être le premier. Puisque c'est CW, si quelqu'un connaît un résultat plus ancien, il corrige simplement le message.
MS Dousti

Réponses:

10
  • Hypothèse: hypothèse de temps exponentielle .
  • Cité pour la première fois dans: Tout en étant du folklore, il a d'abord été formalisé dans l'article suivant: Russell Impagliazzo et Ramamohan Paturi. 1999. La complexité de k-SAT . Dans les actes de la quatorzième conférence annuelle de l'IEEE sur la complexité informatique ( COCO '99 ). IEEE Computer Society, Washington, DC, États-Unis, 237-240.
  • Utilisation (s): Il suppose qu'aucun problème NP-complet ne peut être résolu en temps sous-exponentiel, et implique donc que P ≠ NP.
  • Statut: ouvert.
Incroyable
la source
Je suppose que l'ETH suppose que le problème 3-SAT ne peut pas être résolu en temps sous-exponentiel. Les réponses à ce post ( cstheory.stackexchange.com/questions/3620/… ) impliquent l'existence d'algorithmes temporels sous-exponentiels pour certains problèmes NP-complets tels que Planar Independent Set.
Mohammad Al-Turkistany
Comme l'écrit Mohammad, la description dans «Utilisation (s)» est imprécise ou tout simplement fausse.
Yoshio Okamoto
@YoshioOkamoto: Ceci est un article wiki communautaire. Pourquoi ne pas aller de l'avant et rendre le post précis, voire le corriger?
MS Dousti
Je ne suis pas sûr. La page wikipedia liée contient plus d'informations, et ma modification ne serait qu'une répétition.
Yoshio Okamoto
8
  • Hypothèse : NP n'a pas de p-mesure 0
  • Cité pour la première fois dans : Jack H. Lutz. Catégorie et mesure dans les classes de complexité . SIAM J. Comput. 19: 1100-1131, 1990.
  • μp(NP)0PNP
    1. Tpmp
    2. Il existe une paire de langages disjoints dans NP qui sont inséparables P [4];
    3. α<1nαttp
    4. mp
    5. NP contient un langage P-bi-immun [3];
    6. ENEEENEEEENEE

PNP

  • Statut : Ouvert

[1] J. Lutz et E. Mayordomo. Cook contre Karp / Levin: séparer les notions d'exhaustivité si NP n'est pas petit . Théorète. Comp. Sci. 164: 141-163, 1996.

[2] D. Juedez et J. Lutz. La complexité et la répartition des problèmes difficiles . SIAM J. Comput 24 (2): 279-295, 1995.

[3] E. Mayordomo. Presque chaque ensemble en temps exponentiel est P-bi-immun . Théorète. Comp. Sci. 136: 487-506, 1994.

[4] L. Fortnow, J. Lutz et E. Mayordomo. Inséparabilité et hypothèses fortes pour les paires NP disjointes . Dans Jean-Yves Marion et Thomas Schwentick, éditeurs, Actes du 27e Symposium sur les aspects théoriques de l'informatique, volume 5 de Leibniz International Proceedings in Informatics (LIPIcs), pages 395-404. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Allemagne, 2010.

Joshua Grochow
la source
Excellent. Je crois que vous pouvez retracer l'hypothèse de la thèse de doctorat de Lutz de 1987 " Catégorie et mesure liées aux ressources dans les classes de complexité exponentielle " ou à son article de l'IEEE de 1987 "Catégorie Baire limitée aux ressources et petits circuits dans l'espace exponentiel" (qui n'est pas disponible en ligne !).
MS Dousti
6
  • Hypothèse: NEEEE .
  • Cité pour la première fois dans: Mihir Bellare et Shafi Goldwasser. 1994. La complexité de la décision contre la recherche . SIAM J. Comput. 23, 1 (février 1994), 97-119.
  • Utilisation (s): si l'hypothèse est vraie, il existe des problèmes dans NP dont la version de recherche ne se réduit pas (polynomialement) à leur version de décision. En d'autres termes, dans l'hypothèse donnée, toutes les langues de NP ne sont pas auto-réductibles .
  • Statut: ouvert.
Sadeq Dousti
la source