Complexité des explications facettées en abduction propositionnelle

Résumé L'abduction est un paradigme non monotone populaire qui vise à expliquer des symptômes et manifestations observés. Il a de nombreuses applications, telles que le diagnostic et la planification en intelligence artificielle et les mises à jour de bases de données. Dans l'abduction propositionnelle, nous nous concentrons sur la spécification des connaissances par une formule propositionnelle. La complexité computationnelle des tâches en abduction propositionnelle a été systématiquement caractérisée - même avec des classifications détaillées pour des fragments booléens. Sans surprise, les problèmes de raisonnement les plus éclairants (comptage et énumération) sont très difficiles sur le plan computationnel. Par conséquent, nous considérons le raisonnement entre les décisions et le comptage, ce qui nous permet de mieux comprendre les explications tout en maintenant une complexité favorable. Nous introduisons des facettes dans les abductions propositionnelles, qui sont des littéraux apparaissant dans certaines explications (relevant) mais pas dans toutes les explications (dispensables). Le raisonnement avec des facettes fournit une compréhension plus fine de la variabilité dans les explications (hétérogène). De plus, nous considérons la distance entre deux explications, permettant une meilleure compréhension de l'hétérogénéité/l'homogénéité. Nous analysons de manière exhaustive les facettes de l'abduction propositionnelle dans divers contextes, y compris une caractérisation presque complète dans le cadre de Post.