Complexity results for explanations in the structural-model approach

DOI10.1016/j.artint.2003.06.002zbMath1085.68067OpenAlexW2144312323MaRDI QIDQ814579

Thomas Eiter, Thomas Lukasiewicz

Publication date: 7 February 2006

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

Full work available at URL: https://ora.ox.ac.uk/objects/uuid:ab1af645-5b57-4060-b32e-311337e047a5

zbMATH Keywords

Complexity\(\alpha\)-partial explanationCausal modelExplanationExplanatory powerPartial explanationProbabilistic causal modelWeak cause

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (2)

Probabilistic causes in Markov chains ⋮ Causes and explanations in the structural-model approach: Tractable cases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing functions with parallel queries to NP
• Abduction versus closure in causal theories.
• On the logic of causal explanation
• Axioms of causal relevance
• On truth-table reducibility to SAT
• The computational complexity of abduction
• A taxonomy of complexity classes of functions
• Finding MAPs for belief networks is NP-hard
• Abduction from logic programs: Semantics and complexity
• The complexity of approximating MAPs for belief networks with bounded probabilities
• An algorithm to evaluate quantified Boolean formulae and its experimental evaluation
• Complexity results for structure-based causality.
• Propositional truth maintenance systems: Classification and complexity analysis
• On some tractable classes in deduction and abduction
• A logic of universal causation
• Causes and explanations in the structural-model approach: Tractable cases
• The computational complexity of probabilistic inference using Bayesian belief networks
• Support set selection for abductive and default reasoning
• On the hardness of approximate reasoning
• Bounded Query Classes
• The complexity of logic-based abduction
• Causes and Explanations: A Structural-Model Approach. Part I: Causes
• Causes and Explanations: A Structural-Model Approach. Part II: Explanations
• Probabilistic Evaluation of Counterfactual Queries
• A general scheme for automatic generation of search heuristics from specification \(dependencies^{*}\)

This page was built for publication: Complexity results for explanations in the structural-model approach