Complexity results for structure-based causality.
type: Item
instance of: scholarly article
title: Complexity results for structure-based causality.
zbMATH Open document ID: 1043.68100
DOI: 10.1016/S0004-3702(02)00271-0
author: Thomas Eiter
author: Thomas Lukasiewicz
published in: Artificial Intelligence
publication date: 2003-01-21T00:00:00Z
review text: We give a precise picture of the computational complexity of causal relationships in Pearl's structural models, where we focus on causality between variables, event causality, and probabilistic causality. As for causality between variables, we consider the notions of causal irrelevance, cause, cause in a context, direct cause, and indirect cause. As for event causality, we analyze the complexity of the notions of necessary and possible cause, and of the sophisticated notions of weak and actual cause by Halpern and Pearl. In the course of this, we also prove an open conjecture by Halpern and Pearl, and establish other semantic results. We then analyze the complexity of the probabilistic notions of probabilistic causal irrelevance, likely causes of events, and occurrences of events despite other events. Moreover, we consider decision and optimization problems involving counterfactual formulas. To our knowledge, no complexity aspects of causal relationships in the structural-model approach have been considered so far, and our results shed light on this issue.
Mathematics Subject Classification ID: 68T99
zbMATH DE Number: 1856161
zbMATH Keywords: Causal model
zbMATH Keywords: Probabilistic causal model
zbMATH Keywords: Causality between variables
zbMATH Keywords: Event causality
zbMATH Keywords: Probabilistic causality
zbMATH Keywords: Weak cause
zbMATH Keywords: Actual cause
zbMATH Keywords: Complexity
zbMATH Keywords: Counting hierarchy
describes a project that uses: SATO
MaRDI profile type: Publication
cites work: Probabilistic Evaluation of Counterfactual Queries
cites work: PP is closed under intersection
cites work: The computational complexity of probabilistic inference using Bayesian belief networks
cites work: Causes and explanations in the structural-model approach: Tractable cases
cites work: A logic for reasoning about probabilities
cites work: Axioms of causal relevance
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: On the power of deterministic reductions to C=P
cites work: Q4488092
cites work: Causes and Explanations: A Structural-Model Approach. Part II: Explanations
cites work: Causes and Explanations: A Structural-Model Approach. Part I: Causes
cites work: Q4385525
cites work: Provably correct theories of action
cites work: Q4215779
cites work: Probabilistic logic programming with conditional constraints
cites work: Q3221403
cites work: Q4496846
cites work: On the hardness of approximate reasoning
cites work: Finding MAPs for belief networks is NP-hard
cites work: Complexity classes defined by counting quantifiers
cites work: A logic of universal causation
cites work: The complexity of combinatorial problems with succinct input representation
cites work: More complicated questions about maxima and minima, and some closures of NP
cites work: SATO: An efficient propositional prover
description: scientific article; zbMATH DE number 1856161