The Computational Complexity of Structure-Based Causality
Authors: Gadi Aleksandrowicz, Hana Chockler, Joseph Y. Halpern, Alexander Ivrii
JAIR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Collaboration | Gadi Aleksandrowicz EMAIL IBM Research Lab Haifa, Israel Hana Chockler EMAIL Department of Informatics King s College London, UK Joseph Y. Halpern EMAIL Computer Science Department Cornell University, Ithaca, NY 14853, USA Alexander Ivrii EMAIL IBM Research Lab Haifa, Israel |
| Pseudocode | No | The paper describes algorithms and reductions in paragraph form and logical notation, but does not contain any structured pseudocode or algorithm blocks. For example, the proofs in Appendix A and B describe construction steps but not as formal algorithms. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the methodology described, nor does it provide links to any code repositories. |
| Open Datasets | No | The paper is theoretical and focuses on computational complexity. It does not use or refer to any empirical datasets that would require public access information. Mentions of "binary models" and "general models" refer to types of causal models being analyzed, not specific data. |
| Dataset Splits | No | The paper is theoretical and does not involve experiments with datasets, therefore, there is no mention of training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on computational complexity. It does not describe any experiments that would require specific hardware for execution, and thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on computational complexity. It does not describe any experimental setup or implementation details that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and presents proofs and complexity analysis rather than empirical experiments. Therefore, there are no experimental setup details, hyperparameters, or training configurations mentioned. |