Complexity results for structure-based causality. (Q1852862)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complexity results for structure-based causality. |
scientific article |
Statements
Complexity results for structure-based causality. (English)
0 references
21 January 2003
0 references
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.
0 references
Causal model
0 references
Probabilistic causal model
0 references
Causality between variables
0 references
Event causality
0 references
Probabilistic causality
0 references
Weak cause
0 references
Actual cause
0 references
Complexity
0 references
Counting hierarchy
0 references