OpenAI bouscule une hypothèse clé de l’informatique théorique

OpenAI affirme avoir réfuté l’hypothèse du temps exponentiel, une idée centrale qui suppose que certains cas de 3-SAT exigent un temps de calcul exponentiel. Si cette preuve est confirmée, elle remettrait en cause une limite majeure de l’informatique théorique, sans pour autant résoudre le problème P contre NP. Le résultat, formalisé dans Lean et publié sur GitHub, reste à examiner par des chercheurs indépendants, dont ceux à l’origine de l’hypothèse.

Quand une hypothèse tient depuis des décennies, la facture devient lourde

L’annonce compte surtout pour ce qu’elle touche : un garde-fou théorique qui structure une partie de la recherche en complexité algorithmique. Dans le cas présent, OpenAI dit avoir trouvé une preuve qui contredit l’idée selon laquelle les instances les plus difficiles de 3-SAT imposent forcément un temps exponentiel. Le point décisif n’est pas seulement la thèse elle-même, mais la manière dont elle devra être vérifiée, car la communauté scientifique ne valide pas ce type de résultat sur la seule base d’un communiqué. Une preuve formalisée dans Lean facilite l’examen, mais ne l’abrège pas pour autant.

Une validation encore attendue, et c’est là que tout se joue

Le passage par Lean, un assistant de preuve formelle, réduit le risque d’erreur de logique dans la démonstration. Reste que la publication sur GitHub n’équivaut pas à une validation académique, surtout quand le résultat contredit une hypothèse aussi installée. OpenAI précise que la preuve doit encore être passée au crible indépendamment, notamment par les deux chercheurs associés à l’hypothèse d’origine. En clair, le plus dur commence souvent après l’annonce. L’informatique théorique adore les preuves, mais elle aime encore plus les preuves relues par d’autres.

Pourquoi cette annonce dépasse le seul laboratoire

Si elle se confirme, cette avancée pourrait influencer la manière dont les chercheurs abordent certains problèmes combinatoires et les bornes de calcul que l’on croyait établies. Elle ne mettrait toutefois pas fin au débat P contre NP, qui reste l’un des grands problèmes ouverts de la discipline. La portée réelle dépendra donc moins du caractère spectaculaire de l’annonce que de sa robustesse face à l’examen externe. Pour l’instant, le sujet intéresse surtout la recherche fondamentale, mais les effets symboliques sont déjà nets : quand une hypothèse réputée solide vacille, c’est toute une partie du terrain de jeu qui change de relief.