OpenAI affirme réfuter l'hypothèse du temps exponentiel avec un nouvel algorithme

ChainCatcher rapporte qu'OpenAI a récemment annoncé que son modèle IA a démonté l'hypothèse du temps exponentiel, une conjecture en informatique théorique en vigueur depuis plus de vingt ans, dont l'abréviation anglaise est ETH et non l'ethereum. Cette hypothèse examine la difficulté intrinsèque de problèmes particulièrement complexes, en prenant comme exemple le problème de satisfaisabilité booléenne (SAT) : étant donné un ensemble de conditions logiques, existe-t-il une affectation de valeurs qui satisfasse simultanément toutes les conditions ? À mesure que la taille du problème augmente, la meilleure méthode connue consiste essentiellement à tester chaque solution possible, entraînant une croissance exponentielle du temps de calcul. L'hypothèse du temps exponentiel affirme en outre que ces problèmes ne peuvent pas être accélérés de manière significative et qu'aucun algorithme efficace à temps sous-exponentiel ne peut exister. Depuis sa proposition en 1999, cette hypothèse constitue une pierre angulaire fondamentale de l'informatique théorique, sur laquelle de nombreuses publications s'appuient pour démontrer la difficulté de certains problèmes ou la proximité à l'optimalité de certains algorithmes. Si l'hypothèse du temps exponentiel était réfutée, cela signifierait que certains problèmes considérés comme presque impossibles à accélérer pourraient théoriquement admettre des solutions meilleures. OpenAI affirme avoir découvert un algorithme déterministe capable de compter précisément le nombre de solutions au problème k-SAT en temps sous-exponentiel, et a effectué une vérification formelle à l'aide de Lean. Si ce résultat résiste finalement à l'examen des experts, il remettra directement en question l'hypothèse du temps exponentiel.