OpenAI affirme avoir réfuté l’hypothèse du temps exponentiel, une hypothèse de longue date sur la difficulté de certains problèmes logiques. Le manuscrit, daté du 17 octobre et révisé le 25 octobre, propose un algorithme déterministe qui compte les affectations satisfaisant des formules booléennes en temps sous-exponentiel et avec un espace polynomial. La formalisation dans Lean ne couvre toutefois qu’une borne de temps plus faible que la principale affirmation du manuscrit, et aucun algorithme en temps polynomial ni résolution de P=NP n’est démontré. Des chercheurs, dont Ryan Williams, Russell Impagliazzo et Mohan Paturi, organisent une vérification indépendante sans NDA ni rémunération, tout en précisant que leur participation ne vaut pas certification. Aucun lien pratique avec Bitcoin n’est établi : une attaque necesitarait encore un encodage adapté, une implémentation et une analyse de coût, tandis que les hypothèses de sécurité de Bitcoin reposent sur les logarithmes discrets sur la courbe elliptique secp256k1 et sur les fonctions de hachage.
Source: Lire l’article original
