OpenAI et Anthropic disent que leurs IA ont réfuté une conjecture clé de l’informatique théorique
OpenAI (26 octobre) et Anthropic (27 octobre) affirment que leurs modèles ont trouvé, le même 16 octobre, un algorithme sous-exponentiel pour 3-SAT, ce qui réfuterait l’hypothèse du temps exponentiel posée en 1999 par Impagliazzo et Paturi. Les preuves sont formalisées en Lean ; celle d’Anthropic n’avait été vérifiée par aucun humain à sa publication. Impagliazzo, Paturi et Williams organisent un examen ouvert, sans valeur de certification. L’algorithme ne bat la force brute qu’au-delà de 10^10000 variables : aucun effet pratique, et OpenAI se dit raisonnablement confiante qu’aucun système de chiffrement n’est cassé. OpenAI revendique aussi Kakeya et l’existence de Yang-Mills.
