• jeudi 08 décembre 2005 : salle 06 à château Gombert - CMI
  
  
  • 10h30 : L'abduction propositionnelle est presque toujours difficile - Bruno Zanuttini
    http://www.info.unicaen.fr/~zanutti
    
    Résumé :
    L'abduction est le processus de raisonnement consistant à chercher une explication plausible pour une observation, étant donné une base de connaissances. Par exemple, étant donné la base de connaissances p -> q, pour l'observation q on peut inférer l'explication plausible p. Ce processus est au coeur du raisonnement non monotone, avec des liens en particulier avec la logique des défauts et l'inférence par circonscription. Il a également de nombreuses applications, modélisant en particulier le problème du diagnostic médical ou encore de la configuration interactive.
    
    Dans cet exposé, nous étudierons la complexité de ce processus dans le cadre où les bases de connaissances sont propositionnelles, représentées par des conjonctions de contraintes sur un langage fixé et fini. Les observations seront formalisées par des conjonctions de littéraux et nous demanderons que les explications soient des conjonctions de littéraux formés sur un ensemble donné de variables. Nous montrerons que la complexité du problème de décision (existe-t-il au moins une explication ?) admet une trichotomie, en ce sens que le problème est soit polynomial, soit NP-complet, soit Sigma_2P-complet, et ce selon le language de contraintes fixé pour les bases de connaissances.
    
    Ce résultat montre en particulier que l'abduction est très difficile dans ce formalisme, puisque le seul language polynomial (maximal) est celui contenant la différence et l'égalité binaire. Il permet également de guider la construction de systèmes à base de connaissances lorsque l'abduction est un processus important pour l'application considérée. Enfin, l'exposé présentera en détail les outils utilisés pour parvenir à une telle classification (treillis de Post et formalisme de Schaefer).