Une anthologie des hypothèses de complexité

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 $\Sigma^P_2$ . 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 que$P^{\mathrm{SAT}[k]} = P^{\mathrm{SAT}[k+1]}$$P^{\mathrm{SAT}[k]} \ne P^{\mathrm{SAT}[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 \subseteq \bigcap\limits_{\epsilon > 0} DTIME(2^{n^\epsilon})$
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 .

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

• 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.
• $\mu_p(NP) \neq 0$$P \neq NP$
  1. $\leq_T^p$$\leq_m^p$
  2. Il existe une paire de langages disjoints dans NP qui sont inséparables P [4];
  3. $\alpha < 1$$\leq_{n^{\alpha}-tt}^p$
  4. $\leq_m^p$
  5. NP contient un langage P-bi-immun [3];
  6. $E \neq NE$$EE \neq NEE$$EE \neq NEE$

$P \neq NP$

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

• Hypothèse: NEE ≠ EE .
• 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.