King's College London

Research portal

The computational complexity of structure-based causality

Research output: Chapter in Book/Report/Conference proceedingConference paper

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

Original languageEnglish
Title of host publicationProceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence
Place of PublicationPalo Alto, California
PublisherAAAI Press
Number of pages7
ISBN (Print)9781577356783
Publication statusPublished - 1 Jan 2014
EventTwenty-Eighth AAAI Conference on Articifical Intelligence - Quebec City, Canada
Duration: 27 Jul 201431 Jul 2014


ConferenceTwenty-Eighth AAAI Conference on Articifical Intelligence
Abbreviated titleAAAI-14
CityQuebec City
Internet address


King's Authors


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 σP2- 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 DPk, k = 1,2,3,..of complexity classes is introduced, which generalizes the class Dp introduced by Papadimitriou and Yannakakis DP1) is just We show that the complexity of computing causality under the updated definition is DP2-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.

Download statistics

No data available

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454