The Computational Complexity of Structure-Based Causality
Authors: Gadi Aleksandrowicz, Hana Chockler, Joseph Halpern, Alexander Ivrii
AAAI 2014 | Conference 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. ... We then show that deciding causality under the updated HP definition is DP 2 complete. ... We start by defining the problem formally. ... We are now ready to prove our main result. Theorem 4.4 Lcause and LBcause are DP 2 -complete. |
| Researcher Affiliation | Collaboration | Gadi Aleksandrowicz IBM Research Lab, Haifa, Israel ... Hana Chockler Department of Informatics, King s College, London, UK ... Joseph Y. Halpern Computer Science Department, Cornell University, Ithaca, NY, U.S.A. ... Alexander Ivrii IBM Research Lab, Haifa, Israel |
| Pseudocode | No | The paper does not contain any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention providing open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve training models on datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not report on experiments requiring hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not specify software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. |