ETH et 3-SAT : perdre une borne ne donne pas un algorithme
Contenu de l'épisode
Et si l'hypothèse du temps exponentiel (ETH) tombait vraiment, comme le revendiquent les récents travaux d'OpenAI et d'Anthropic ? Entre le vertige théorique discuté début novembre et la réalité des constantes cachées, perdre une barrière mathématique ne suffit pas à accélérer nos logiciels. Cet épisode décrypte pourquoi une borne en 2^{o(n)} n'est pas un gain pratique et comment les équipes R&D doivent arbitrer leurs recherches face à des conjectures fragilisées.
#modeles #meta-volatile #complexite #algorithmes #3sat