AbstractAbduction is an important form of nonmonotonic reasoning allowing one to find explanations for certain symptoms or manifestations. When the application domain is described by a logical theory, we speak about logic-based abduction. Candidates for abductive explanations are usually subjected to minimality criteria such as subset-minimality, minimal cardinality, minimal weight, or minimalityunder prioritization of individual hypotheses. This paper present a comprehensive complexity analysis of relevant decision and search problems related to abduction on propositional theories. Our results indicate that abduction is harder than deduction. In particular, we show that with the most basic forms of abduction the relevant decision problems are complete for complexity classes at the second level of the polynomial hierarchy, while the use of prioritization raises the complexity to the third level in certain cases. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: I.2.3 [Artificial Intelligence]: Deduction and Theorem Proving; I.2.4 [Artificial Intelligence]: Knowledge Representation Formalisms and Methods; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic
General Terms: Theory
Additional Key Words and Phrases: Abduction, Complexity Analysis, Diagnosis, Reasoning, Propositional Logic
Selected papers that cite this one
- Thomas Eiter, Georg Gottlob, and Nicola Leone. Abduction from logic programs: Semantics and complexity. Theoretical Computer Science, 189(1-2):129-177, 15 December 1997.
Selected references
- Drew McDermott. Nonmonotonic logic II: Nonmonotonic modal theories. Journal of the ACM, 29(1):33-57, January 1982.
- A. R. Meyer and L. J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In 13th Annual Symposium on Switching and Automata Theory, pages 125-129, The University of Maryland, 25-27 October 1972. IEEE.
- L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: Preliminary report. In Conference Record of Fifth Annual ACM Symposium on Theory of Computing, pages 1-9, Austin, Texas, 30 April-2 May 1973.