Il y a dix ans, j'écrivais dans une page de discussion de Wikipédia :

«  une fois qu'un problème est démontré NP-complet, on cherche des algorithmes exponentiels mais efficaces en pratique ... une fois que j'ai démontré qu'un truc était NP- ou PSPACE-complet, je considère que c'est une bouse insoluble en général »

Évidemment, un problème NP-complet (ou, pire, PSPACE-complet) est toujours insoluble en pratique si on le prend dans toute sa généralité. J'ai cependant évolué sur mon ressenti qu'un problème NP-complet était une « bouse ».

En 2004, je travaillais sur un outil d'analyse statique nommé Astrée où nous traquions les causes d'inefficacité. Un simple algorithme linéaire mal placé pouvait rendre l'outil inutilisable... Autant dire que l'idée de résoudre des problèmes NP-complets au milieu de l'analyseur me semblait pour le moins saugrenue !

Lorsque j'ai vu des articles prétendant trouver des collisions ou autres attaques de sécurité sur des primitives cryptographiques par réduction à SAT, j'étais franchement sceptique. J'avais implémenté une passe (non documentée) dans Astrée qui convertissait des problèmes d'analyse statique sur des fonctions sans boucles vers des formules SAT... on pouvait très vite faire exploser les solveurs SAT tels que zChaff simplement en demandant de prouver la commutativité de la multiplication d'entiers 32 bits !

Depuis, j'utilise régulièrement des SMT-solveurs, qui résolvent des problèmes NP-complets ou pire. J'ai même été au comité de programme de conférences spécialisées dans ce domaine, j'ai publié divers articles sur la combinaison de SMT-solving et d'autres méthodes d'analyse statique ainsi que sur la décision efficace de certaines classes de formule par SMT-solving.

Qu'est-ce qui a changé ? Sans doute le fait que, depuis 10 ans, on a développé des outils réellement efficaces en pratique sur de bonnes classes de formules. Aussi, chez moi, l'idée que même si l'outil explose combinatoirement sur une classe de problèmes, on arrivera, en changeant la présentation du problème, à éviter ou repousser l'explosion ; bref que, même en analyse de programmes, on peut utiliser des « coupes » comme on le fait en recherche opérationnelle (j'ai soumis dernièrement un article sur l'application de cette idée à la recherche de plus grand temps d'exécution).

Pour tout dire, je n'ai même plus trop peur des problèmes EXPTIME-durs, voire NEXPTIME-complets ! Vous me direz, c'est bien normal, après tout je fais de l'analyse de programmes et c'est indécidable... Mais, psychologiquement, il y a 10 ans j'aurais considéré que se réduire au fragment de Bernays-Schönfinkel (NEXPTIME-complet) c'était de la pure théorie sans application.

Bref, est-ce le monde ou moi qui avons changé ? Sans doute les deux.