1886

L’étude des problèmes de raisonnement est un domaine de recherche très actif en intelligence artificielle. La majorité de ces problémes sont algorithmiquement difficile puisqu’ils se situent au deuxième niveau de la hiérarchie polynomiale. Identifier des fragments de la logique propositionnelle dans lesquels ces problèmes sont plus faciles a résoudre est un des challenges récents dans le domaine de la représentation des connaissances. Beaucoup de ces problèmes font intervenir des contraintes de minimalite et il s’avère que comprendre précisement la complexité du problème suivant est crucial :
CardMinSat: Etant donné une formule propositionnelle Phi et une variable x, x est-elle vraie dans un modèle de Phi de cardinalité minimale?
Notre objectif est de déterminer la complexité de ce problème dans des fragments de la logique propositionnelle. L’algèbre universelle qui établit une connection de Galois entre le treillis des relations booléennes (co-clones) et celui des fonctions booléennes (clones) est désormais reconnue comme un outil très puissant pour obtenir la classication en complexité de divers problèmes liés a la satisfaisabilité. Cependant la contrainte de minimalité qui apparait ici rend l’application de cette connection inappropriée. Il faut étudier un raffinement de ce treillis, celui des co-clones partiels « gelés ». Ce faisant nous avons espoir d’être en mesure de comprendre la complexité du problème CardMinSat dans divers fragments de la logique propostionnelle. Ce serait la pierre angulaire d’un projet plus ambitieux visant à étudier de façon systématique la complexité de différents problèmes de raisonnement dans des fragments de la logique propostionnelle.