The computational complexity of abduction

DOI10.1016/0004-3702(91)90005-5zbMath0737.68076MaRDI QIDQ1182159

Tom Bylander, Dean Allemang, Michael C. Tanner, John R. Josephson

Publication date: 28 June 1992

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(91)90005-5

zbMATH Keywords

computational complexity; NP-hard; explanation; abduction

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

On an open problem in classification of languages, AN ARTIFICIAL NETWORK FOR REASONING IN THE CANCELLATION CLASS WITH APPLICATION TO THE DIAGNOSIS OF CELLS DIVISION, Special issue. Model-based reasoning in science: learning and discovery, Mathematical aspects of concept analysis, Complexity results for explanations in the structural-model approach, Multi-modal diagnosis combining case-based and model-based reasoning: a formal and experimental analysis, Perceiving the infinite and the infinitesimal world: unveiling and optical diagrams in mathematics, Counting complexity of propositional abduction, Analysis of notions of diagnosis, The approximation of implicates and explanations, The complexity of propositional closed world reasoning and circumscription, Abduction from logic programs: Semantics and complexity, Semantics and complexity of abduction from default theories, Process algebras for systems diagnosis., Model-based reasoning about learner behaviour, What makes propositional abduction tractable, Abductive reasoning in neural-symbolic systems, Reasoning through doing. Epistemic mediators in scientific discovery

Uses Software

• MOLE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fusion, propagation, and structuring in belief networks
• Distributed revision of composite beliefs
• Diagnosing multiple faults
• A theory of diagnosis from first principles
• The computational complexity of probabilistic inference using Bayesian belief networks
• A Probabilistic Causal Model for Diagnostic Problem Solving Part I: Integrating Symbolic Causal Inference with Numeric Probabilistic Inference
• A Probabilistic Causal Model for Diagnostic Problem Solving Part II: Diagnostic Strategy
• The Complexity of Enumeration and Reliability Problems