The computational complexity of structure-based causality

DOI10.1613/JAIR.5229MaRDI QIDQ2974511zbMATH OpenOpenAlexFDO

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

Publication date 10 April 2017

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.3076

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in artificial intelligence (68T27)

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 Sigma_2^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_k^P, k= 1, 2, 3, ..., of complexity classes is introduced, which generalizes the class DP introduced by Papadimitriou and Yannakakis (DP is just D_1^P). %joe2 %We show that the complexity of computing causality is $D_2$-complete %under the new definition. Chockler and Halpern citeyear{CH04} extended the We show that the complexity of computing causality under the updated definition is $D_2^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.

Recommendations

• Complexity results for structure-based causality.
• Complexity results for explanations in the structural-model approach
• Causes and explanations in the structural-model approach: Tractable cases
• Actual causality
• Causes and Explanations: A Structural-Model Approach. Part I: Causes

Cited in

(18)

• Uncovering deterministic causal structures: a Boolean approach
• Complexity results for structure-based causality.
• Causal computational complexity of distributed processes
• scientific article; zbMATH DE number 4203674 (Why is no real title available?)
• scientific article; zbMATH DE number 2040707 (Why is no real title available?)
• Actual causality
• scientific article; zbMATH DE number 2243367 (Why is no real title available?)
• Equilibrium design for concurrent games
• IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING?
• From Checking to Inference: Actual Causality Computations as Optimization Problems
• A glance at causality theories for artificial intelligence
• A theory of fine-grained lineage for functions on structured objects
• Counterfactuals modulo temporal logics
• Designing equilibria in concurrent games with social welfare and temporal logic constraints
• A rule-based modal framework for causal reasoning
• Complexity results for explanations in the structural-model approach
• Foundations of fine-grained explainability
• Computational complexity of determining which statements about causality hold in different space-time models

This page was built for publication: The computational complexity of structure-based causality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2974511)