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

computational complexityabductionpropositional logicPost's latticeBoolean connective

Mathematics Subject Classification ID

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

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

(12)

• The Complexity of Circumscriptive Inference in Post’s Lattice
• Propositional truth maintenance systems: Classification and complexity analysis
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• Parameterized complexity of abduction in Schaefer's framework
• Complexity Classifications for Logic-Based Argumentation
• A Complete Classification of the Complexity of Propositional Abduction
• What makes propositional abduction tractable
• On the complexity of second-best abductive explanations
• On the complexity of the clone membership problem
• Counting complexity of propositional abduction
• Counting Complexity of Minimal Cardinality and Minimal Weight Abduction
• The weight in enumeration

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)