# The Computational Complexity of Structure-Based Causality

arXiv: https://arxiv.org/abs/1412.3076 · HTML: https://mlsanity.com/paper/1412.3076/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Dec 2014.

## Built on by (most cited first, 12 of 12)

- [The Hardness of Reasoning about Probabilities and Causality](https://mlsanity.com/paper/2305.09508/) (2023)
- [Automated Discovery of Functional Actual Causes in Complex Environments](https://mlsanity.com/paper/2404.10883/) (2024)
- [Towards Computationally Efficient Responsibility Attribution in Decentralized Partially Observable MDPs](https://mlsanity.com/paper/2302.12676/) (2023)
- [Equilibrium Design for Concurrent Games](https://mlsanity.com/paper/2106.10192/) (2021)
- [Analyzing Intentional Behavior in Autonomous Agents under Uncertainty](https://mlsanity.com/paper/2307.01532/) (2023)
- [Counterfactuals Modulo Temporal Logics](https://mlsanity.com/paper/2306.08916/) (2023)
- [Searching for Actual Causes: Approximate Algorithms with Adjustable Precision](https://mlsanity.com/paper/2507.07857/) (2025)
- [Binary Spiking Neural Networks as Causal Models](https://mlsanity.com/paper/2604.27007/) (2026)
- [Actual causality in fault trees](https://mlsanity.com/paper/2607.01840/) (2026)
- [Computing Actual Causes for Neural Network Predictions under Structured Causal Inputs](https://mlsanity.com/paper/2608.03772/) (2026)
- [HANSARD: A Reference Architecture for Forensic Readiness, Runtime Witnessing, and Graded Attribution in Autonomous Multi-Agent AI Systems](https://mlsanity.com/paper/2608.22512/) (2026)
- [Certifying Interventional Agreement Among Observationally Equivalent Causal Models](https://mlsanity.com/paper/2609.32247/) (2026)

## Abstract (arXiv)

Halpern and Pearl introduced a definition of actual causality; Eiter and Lukasiewicz showed that computing whether X=x is a cause of Y=y is NP-complete in binary models (where all variables can take on only two values) and Sigma2P-complete in general models. In the final version of their paper, Halpern and Pearl slightly modified the definition of actual cause, in order to deal with problems pointed by Hopkins and Pearl. As we show, this modification has a nontrivial impact on the complexity of computing actual cause. To characterize the complexity, a new family DkP, k= 1, 2, 3, ..., of complexity classes is introduced, which generalizes the class DP introduced by Papadimitriou and Yannakakis (DP is just D1P). %joe2 %We show that the complexity of computing causality is D2-complete %under the new definition. Chockler and Halpern citeyearCH04 extended the We show that the complexity of computing causality under the updated definition is D2P-complete. Chockler and Halpern extended the definition of causality by introducing notions of responsibility and blame. The complexity of determining the degree of responsibility and blame using the original definition of causality was completely characterized. Again, we show that changing the definition of causality affects the complexity, and completely characterize it using the updated definition.