NONMONOTONIC REASONING - FROM COMPLEXITY TO ALGORITHMS

The purpose of this paper is to outline various results regarding the computational complexity and the algorithms of nonmonotonic entailment in different coherence-based approaches. Starting from a (non necessa rily consistent) belief base E and a pre-order on E, we first present different mechanisms for selecting preferred consistent subsets. Then we present different entailment principles in order to manage these mu ltiple subsets. The crossing point of each generation mechanism m and each entailment principle p defines an entailment relation (E, less th an or equal to) (sic) (p.m) Phi which we study from the computational complexity point of view. The results are not very encouraging since t he complexity of all these nonmonotonic entailment relations is, in mo st restricted languages, larger than the complexity of monotonic entai lment. So, we decided to extend Binary Decision Diagrams technics, whi ch are well suited to the task of solving NP-hard logic-based problems . Both theoretical and experimental results are described along this l ine in the last sections.