OpenAI et Anthropic affirment avoir réfuté l’hypothèse du temps

Résumé

OpenAI et Anthropic affirment que leurs modèles ont trouvé des algorithmes remettant en cause l’ETH, une hypothèse centrale de la complexité algorithmique.

Les faits

OpenAI a publié des solutions à trois problèmes mathématiques majeurs qui préoccupent les chercheurs depuis longtemps. L’une d’elles conteste l’hypothèse du temps exponentiel, ou ETH, une hypothèse durable de l’informatique théorique qui joue un rôle important dans la compréhension des problèmes difficiles à calculer. L’ETH s’inscrit dans le débat plus large sur P contre NP. Elle affirme que, pour une catégorie précise de problèmes logiques difficiles, même le meilleur algorithme nécessite un temps exponentiel lorsque le nombre de variables augmente. Les modèles d’OpenAI et d’Anthropic auraient toutefois produit des algorithmes capables de résoudre ces problèmes en temps « sous-exponentiel », c’est-à-dire plus rapidement que ce que l’on pensait possible. Levent Alpöge, mathématicien chez Anthropic, a suggéré qu’OpenAI s’appuyait sur des travaux existants. Quelques heures plus tard, Anthropic a publié sa propre réfutation de l’ETH. Face à ces résultats, les informaticiens ont constitué un groupe de travail et demandé que les démonstrations soient rendues publiques. Ryan Williams, professeur au MIT chargé d’organiser la réponse de son domaine, a décrit certaines parties de la démonstration d’OpenAI comme « routinières », mais a aussi évoqué « deux ou trois parties d’un autre monde ». Il a déclaré que ces éléments devaient être étudiés collectivement par la communauté scientifique.

Pourquoi c’est important

Si les affirmations des deux laboratoires résistent à l’examen, elles remettraient en cause de nombreux travaux informatiques qui utilisent l’ETH depuis une dizaine d’années. Les chercheurs devraient alors déterminer comment adapter les fondements théoriques du domaine et quelles conséquences en tirer pour la relation entre les classes P et NP. L’enjeu concerne également la cybersécurité. Ryan Williams a indiqué qu’un algorithme amélioré pourrait fragiliser des systèmes cryptographiques reposant sur certaines tailles de clés. OpenAI lui aurait toutefois assuré avoir vérifié cette question et être raisonnablement convaincue qu’aucune compromission cryptographique n’en découlait.

Questions fréquentes

Qu’est-ce que l’hypothèse du temps exponentiel ?

L’ETH affirme que certains problèmes logiques exigent un temps exponentiel lorsque le nombre de variables augmente, même avec le meilleur algorithme.

Que revendiquent OpenAI et Anthropic ?

Les deux laboratoires affirment que leurs modèles ont produit des algorithmes résolvant ces problèmes en temps « sous-exponentiel ».

Quel est le lien avec P contre NP ?

L’ETH appartient au débat P contre NP et pourrait, si elle était réfutée, ouvrir une voie vers des algorithmes établissant plus largement P = NP.

Quelles pourraient être les conséquences pour la cryptographie ?

Un algorithme amélioré pourrait remettre en cause certains systèmes reposant sur des tailles de clés précises, mais OpenAI affirme ne pas avoir identifié de faille de ce type.

Source

Auteur

Rédaction spécialisée dans la veille et l’analyse de l’actualité de l’intelligence artificielle, des puces IA, des robots, des agents IA et de la recherche.