Complexity results for structure-based causality.

DOI10.1016/S0004-3702(02)00271-0zbMath1043.68100MaRDI QIDQ1852862

Thomas Eiter, Thomas Lukasiewicz

Publication date: 21 January 2003

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

zbMATH Keywords

ComplexityCausal modelProbabilistic causal modelWeak causeActual causeCausality between variablesCounting hierarchyEvent causalityProbabilistic causality

Mathematics Subject Classification ID

Artificial intelligence (68T99)

Related Items

Foundations of fine-grained explainability, IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING?, The resilience of conjunctive queries with inequalities, The parameterized complexity and kernelization of resilience for database queries, Explaining counterexamples using causality, Identification of structures and causation in flow graphs, Causes and explanations in the structural-model approach: Tractable cases, Compilation of static and evolving conditional knowledge bases for computing induced nonmonotonic inference relations, APPROPRIATE CAUSAL MODELS AND THE STABILITY OF CAUSATION, Explanation in artificial intelligence: insights from the social sciences, Complexity results for explanations in the structural-model approach

Uses Software

• SATO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of combinatorial problems with succinct input representation
• More complicated questions about maxima and minima, and some closures of NP
• Axioms of causal relevance
• Finding MAPs for belief networks is NP-hard
• A logic for reasoning about probabilities
• PP is closed under intersection
• 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
• On the hardness of approximate reasoning
• Probabilistic logic programming with conditional constraints
• On the power of deterministic reductions to C=P
• Computational Complexity of Probabilistic Turing Machines
• Complexity classes defined by counting quantifiers
• Provably correct theories of action
• SATO: An efficient propositional prover
• 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