Complexity results for structure-based causality

By Thomas Eiter, Thomas Lukasiewicz. 2001

110 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Causal Inference & Discovery

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Causal Inference & Discovery

Citations in the corpus

Explanation in Human-AI Systems: A Literature Meta-Review, Synopsis of Key Ideas and Publications, and Bibliography for Explainable AI (2019, background): “…includes: Ahn (1998); Ahn et al. (1995); Ahn and Kalish (2000); Chater and Oaksford, (2006); Cheng (1997, 2000); Einhorn and Hogarth (1986); Eiter and Lukasiewicz (2002, 2006); Feltovich, Hoffman, Woods, and Roesler (2004); Graesser, Baggett, and Williams (1996); Halpern and Pearl…”
Explainable AI: Beware of Inmates Running the Asylum Or: How I Learnt to Stop Worrying and Love the Social and Behavioural Sciences (2017, methodology): “For explainable AI models, these heuristics are useful from a computational perspective in large causal chains, in which causal attribution is intractable in many cases [Eiter and Lukasiewicz, 2002].”
Explanation in Artificial Intelligence: Insights from the Social Sciences (2017, background): “This is a general model that should be accessible to anyone with a computer science background, has been adopted by philosophers and psychologists, and is accompanied by many additional results, such as an axiomatisation [57] and a series articles on complexity analysis [40, 41].”
Responsibility and blame: a structural-model approach (2003, unknown): “It is shown in [Eiter and Lukasiewicz 2002a] thatX = 0 is a cause of ψ in (M,~u) iff Φ ∈ TQBF.”