The computational complexity of structure-based causality

Gadi Aleksandrowicz, Hana Chockler, Joseph Y. Halpern, Alexander Ivrii

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)
222 Downloads (Pure)

Abstract

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 ΣP 2 -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 out by Hopkins and Pearl. As we show, this modification has a nontrivial impact on the complexity of computing whether →X = →x is a cause of Y = y. To characterize the complexity, a new family DP k , k = 1; 2; 3; ⋯, of complexity classes is introduced, which generalizes the class DP introduced by Papadimitriou and Yannakakis (DP is just DP 1 ).We show that the complexity of computing causality under the updated definition is DP 2 -complete. Chockler and Halpern 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.

Original languageEnglish
Pages (from-to)431-451
Number of pages21
JournalJournal Artificial Intelligence Research
Volume58
Early online date27 Feb 2017
DOIs
Publication statusPublished - Feb 2017

Keywords

  • causality
  • complexity
  • responsibility
  • blame

Fingerprint

Dive into the research topics of 'The computational complexity of structure-based causality'. Together they form a unique fingerprint.

Cite this