The computational complexity of structure-based causality

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

The computational complexity of structure-based causality

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

^*Corresponding author for this work

Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

11 Citations (Scopus)

203 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₂- 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 D_P^k, k = 1,2,3,..of complexity classes is introduced, which generalizes the class D^p introduced by Papadimitriou and Yannakakis D^P₁) is just We show that the complexity of computing causality under the updated definition is D^P₂-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.

Original language	English
Title of host publication	Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence
Place of Publication	Palo Alto, California
Publisher	AAAI Press
Pages	974-980
Number of pages	7
Volume	2
ISBN (Print)	9781577356783
Publication status	Published - 1 Jan 2014
Event	Twenty-Eighth AAAI Conference on Articifical Intelligence - Quebec City, Canada Duration: 27 Jul 2014 → 31 Jul 2014 https://www.aaai.org/Conferences/AAAI/aaai14.php

Conference

Conference	Twenty-Eighth AAAI Conference on Articifical Intelligence
Abbreviated title	AAAI-14
Country/Territory	Canada
City	Quebec City
Period	27/07/2014 → 31/07/2014
Internet address	https://www.aaai.org/Conferences/AAAI/aaai14.php

Access to Document

The Computational Complexity of Structure-Based CausalityAccepted author manuscript, 379 KB

https://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8328

Cite this

@inbook{f171fab221e2432e9750b94de488a067,

title = "The computational complexity of structure-based causality",

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 σ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.",

author = "Gadi Aleksandrowicz and Hana Chockler and Halpern, {Joseph Y.} and Alexander Ivrii",

year = "2014",

month = jan,

day = "1",

language = "English",

isbn = "9781577356783",

volume = "2",

pages = "974--980",

booktitle = "Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence",

publisher = "AAAI Press",

note = "Twenty-Eighth AAAI Conference on Articifical Intelligence, AAAI-14 ; Conference date: 27-07-2014 Through 31-07-2014",

url = "https://www.aaai.org/Conferences/AAAI/aaai14.php",

}

Aleksandrowicz, G, Chockler, H, Halpern, JY & Ivrii, A 2014, The computational complexity of structure-based causality. in Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. vol. 2, AAAI Press, Palo Alto, California, pp. 974-980, Twenty-Eighth AAAI Conference on Articifical Intelligence, Quebec City, Canada, 27/07/2014. <https://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8328>

TY - CHAP

T1 - The computational complexity of structure-based causality

AU - Aleksandrowicz, Gadi

AU - Chockler, Hana

AU - Halpern, Joseph Y.

AU - Ivrii, Alexander

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

M3 - Conference paper

AN - SCOPUS:84908150555

SN - 9781577356783

VL - 2

SP - 974

EP - 980

BT - Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence

PB - AAAI Press

CY - Palo Alto, California

T2 - Twenty-Eighth AAAI Conference on Articifical Intelligence

Y2 - 27 July 2014 through 31 July 2014

ER -

The computational complexity of structure-based causality

Abstract

Conference

Access to Document

Fingerprint

Cite this