Complexity classifications for propositional abduction in Post's framework

DOI10.1093/LOGCOM/EXR012MaRDI QIDQ3165755zbMATH OpenOpenAlexFDO

Authors

Publication date 19 October 2012

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.4923

zbMATH Keywords

abductionBoolean connectivecomputational complexityPost's latticepropositional logic

Mathematics Subject Classification ID

Classical propositional logic (03B05) Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Abstract: In this paper we investigate the complexity of abduction, a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining the world's behavior it aims at finding an explanation for some observed manifestation. In this paper we consider propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be SigPtwo-complete in general. We focus on formulae in which the allowed connectives are taken from certain sets of Boolean functions. We consider different variants of the abduction problem in restricting both the manifestations and the hypotheses. For all these variants we obtain a complexity classification for all possible sets of Boolean functions. In this way, we identify easier cases, namely NP-complete, coNP-complete and polynomial cases. Thus, we get a detailed picture of the complexity of the propositional abduction problem, hence highlighting sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.

Recommendations

• A Complete Classification of the Complexity of Propositional Abduction
• What makes propositional abduction tractable
• scientific article; zbMATH DE number 512816
• The Complexity of Abduction for Equality Constraint Languages
• The complexity of logic-based abduction

Cited in

(14)

• Propositional truth maintenance systems: Classification and complexity analysis
• On the complexity of the clone membership problem
• Parameterised complexity of abduction in Schaefer's framework
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• What makes propositional abduction tractable
• Complexity Classifications for Logic-Based Argumentation
• Counting Complexity of Minimal Cardinality and Minimal Weight Abduction
• The Complexity of Circumscriptive Inference in Post’s Lattice
• scientific article; zbMATH DE number 512816 (Why is no real title available?)
• Parameterized complexity of abduction in Schaefer's framework
• A Complete Classification of the Complexity of Propositional Abduction
• The weight in enumeration
• On the complexity of second-best abductive explanations
• Counting complexity of propositional abduction

This page was built for publication: Complexity classifications for propositional abduction in Post's framework

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3165755)