Tractable reasoning in artificial intelligence (Q1894662)

This book is concerned with computational complexity aspects of the logical approach to artificial intelligence. The focus is on two strategies for achieving computational tractability in knowledge representation and reasoning. The first strategy is language restriction: the language used for representing knowledge is restricted so that the formalization of interesting cases is still possible, but the resulting tasks are computationally feasible. The second strategy is theory approximation: a form of logic is approximated by using another one that is characterized by a weaker level of inferential power but is computationally feasible even with a full expressiveness in the language. As far as the language restriction strategy is concerned, a form of nonmonotonic reasoning called minimal reasoning is considered. Closed-world reasoning and circumscription are two forms of minimal reasoning addressed in this book. Tractability thresholds of several problems are analyzed, finding polynomially tractable cases (for which polynomial-time algorithms are given) and intractable cases. Propositional as well as first-order formulae are considered, decisions as well as constructive problems, modeling several reasoning patterns. Complexity results are applied to obtain efficient strategies for the solution of reasoning problems like nonmontonic inheritance and model-based diagnosis. As far as theory approximation is concerned, a strategy for the approximation of decision reasoning problems is defined based on multivalued logic. This strategy is applied to a wide range of reasoning problems in propositional logic, fragments of first-order logic (concept description languages), propositional nonmonotonic logics, and modal logics. Finally, a metalevel language for the representation of approximate knowledge owned by a non-omniscient agent is defined.