Summary: The third author and J. Pearl [“Causes and explanations: a structural-model approach. I: Causes”, in: Proceedings of the 17th annual conference on uncertainity in artificial intelligence, UAI’01. San Francisco: Morgan Kaufmann. 194–202 (2001)] introduced a definition of actual causality; T. Eiter and T. Lukasiewicz [Artif. Intell. 142, No. 1, 53–89 (2002; Zbl 1043.68100)] 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 \(\Sigma^{\mathrm{P}}_2\)-complete in general models. In the final version of their paper [Br. J. Philos. Sci. 56, No. 4, 843–887 (2005; Zbl 1092.03003)], the third author and J. Pearl slightly modified the definition of actual cause, in order to deal with problems pointed out by M. Hopkins and J. Pearl [“Clarifying the usage of structural models for commonsense causal reasoning”, in: Proceedings of the AAAI spring symposium on logical formalizations of commonsense reasoning, 2003. Palo Alto, CA: Association for the Advancement of Artificial Intelligence (AAAI) Press. 83–89 (2003)]. As we show, this modification has a nontrivial impact on the complexity of computing whether \(\vec{X}=\vec{x}\) is a cause of \(Y=y\). To characterize the complexity, a new family \(D_k^{\mathrm{P}}\), \(k=1, 2, 3,\ldots\), of complexity classes is introduced, which generalises the class \(D^{\mathrm{P}}\) introduced by C. H. Papadimitriou and M. Yannakakis [J. Comput. Syst. Sci. 28, 244–259 (1984; Zbl 0571.68028)] (\(D^{\mathrm{P}}\) is just \(D_1^{\mathrm{P}}\)). We show that the complexity of computing causality under the updated definition is \(D_2^{\mathrm{P}}\)-complete.
The second and the third author [J. Artif. Intell. Res. (JAIR) 22, 93–115 (2004; Zbl 1080.68680)] extended the definition of causality by introducing notions of responsibility and blame, and characterized the complexity of determining the degree of responsibility and blame using the original definition of causality. Here, we completely characterize the complexity using the updated definition of causality. In contrast to the results on causality, we show that moving to the updated definition does not result in a difference in the complexity of computing responsibility and blame.