Des laboratoires d'IA de pointe affirment avoir réfuté l'hypothèse du temps exponentiel

OpenAI a annoncé avoir résolu trois problèmes mathématiques majeurs, dont la réfutation de l'Exponential Time Hypothesis (ETH), une hypothèse centrale en informatique théorique. Selon l'annonce, ses modèles ont proposé des algorithmes résolvant des problèmes NP en temps « sous-exponentiel », plus rapide que ce que l'ETH permettait jusqu'alors. Anthropic a rapidement emboîté le pas en publiant sa propre réfutation de l'ETH, déclenchant une vague de réactions dans la communauté scientifique.

OpenAI a structuré ses annonces différemment selon les disciplines : dépôt sur GitHub pour les mathématiciens, création d'un groupe de travail pour les informaticiens, et formation d'un autre pour les physiciens. MIT Professor Ryan Williams, spécialiste de la complexité algorithmique, a critiqué par le passé les méthodes d'OpenAI mais collabore désormais avec le laboratoire pour analyser ces résultats. Il souligne que certaines parties des preuves proposées par OpenAI semblent innovantes, tandis que d'autres relèvent de travaux existants. Les chercheurs appellent à une discussion collective pour évaluer l'impact de ces découvertes.

L'ETH est liée au problème P vs NP, un enjeu majeur en informatique depuis des décennies. Si les résultats d'OpenAI et Anthropic se confirment, ils pourraient remettre en cause des fondements théoriques utilisés dans de nombreux travaux scientifiques et impliquer des avancées cryptographiques. Williams tempère cependant l'enthousiasme, estimant que ces résultats ne sont probablement pas définitifs et soulignant les défis éducatifs et méthodologiques posés par l'IA dans la recherche fondamentale.