OpenAI affirme avoir réfuté l’hypothèse du temps exponentiel (ETH), une conjecture informatique de 1999 sans lien avec Ethereum, sa cotation ou son cofondateur Vitalik Buterin. Son article de 67 pages présente un algorithme déterministe capable de compter les solutions du problème 3-SAT en temps sous-exponentiel, ce qui, selon l’entreprise, pourrait ouvrir la voie à de meilleurs algorithmes. La démonstration a été formalisée dans Lean et est soumise à un examen indépendant dirigé par Russell Impagliazzo, Ramamohan Paturi et Ryan Williams, qui précise que sa participation ne vaut pas certification. Cette avancée ne résout toutefois pas le problème P contre NP et n’a pas encore dapplications pratiques immédiates. Anthropic a de son côté présenté un algorithme similaire découvert par un modèle de recherche de Claude, en précisant qu’il ne concerne que l’analyse asymptotique.
Source: Lire l’article original
