Bruno Zanuttini (GREYC, Caen)

Le problème consistant à décider si une formule propositionnelle donnée a au moins un modèle est NP-complet dans le cas général. Je montrerai comment on peut torturer certaines classes de formules, en leur retirant de l’expressivité pour chercher à leur faire renoncer à cette arrogante difficulté algorithmique. Toutefois, certaines classes résistent malgré l’acharnement sadique des bourreaux. Nous cherchons les limites de cette résistance, en cherchant les plus grandes maltraitances auxquelles elles résistent. Nous les abaissons ainsi vers la limite entre la NP-complétude et le temps polynomial, là où résideraient des problèmes intrinsèquement sous- exponentiels, si toutefois il en existe.

Les techniques utilisées pour ce travail reposent notamment sur l’expressivité des langages de contraintes, que l’on étudie avec un point de vue algébrique. Je présenterai notamment la notion de co-clone “gelé”. Ces techniques font sens pour l’intelligence artificielle et la représentation de connaissances, ainsi que pour mesurer la “déclarativité” des langages de contraintes. C’est un point de vue peu développé en dehors des introductions d’articles qui cherchent à motiver le travail présenté, mais j’essaierai de vous convaincre que l’intérêt en est réel.

Ce travail est mené en collaboration avec Victor Lagerkvist, Gustav Nordh et Peter Jonsson, de l’université de Linköping, en Suède. Mais il n’y a aucun lien avec la dénomination de “co-clone gelé”, bien entendu.