← Glossaire Terme
Exponential Time Hypothesis
Une hypothèse largement reconnue en informatique selon laquelle certaines énigmes logiques difficiles ne peuvent pas être résolues rapidement dans le pire des cas.
Le Exponential Time Hypothesis indique que pour un type de puzzle célèbre, appelé SAT (trouver des valeurs qui rendent une déclaration logique vraie), il n’existe pas de raccourci intelligent. Dans le pire des cas, le temps nécessaire double à peu près avec chaque variable supplémentaire, ce qui devient très rapidement impossible.
Personne ne l’a prouvé, mais des centaines d’articles de recherche supposent que c’est vrai et s’appuient sur cela. Si quelqu’un le réfutait réellement, ces articles perdraient leur fondement, même si leurs résultats pouvaient encore être corrects.
Mentionné dans