Complexity Results for Explanations in the Structural−Model Approach
<p>We analyze the computational complexity of Halpern and Pearl's (causal) explanations in the structural-model approach, which are based on their notions of weak and actual causality. In particular, we give a precise picture of the complexity of deciding explanations, alpha-partial expla...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Morgan Kaufmann
2002
|
| _version_ | 1826290361700450304 |
|---|---|
| author | Eiter, T Lukasiewicz, T |
| author_facet | Eiter, T Lukasiewicz, T |
| author_sort | Eiter, T |
| collection | OXFORD |
| description | <p>We analyze the computational complexity of Halpern and Pearl's (causal) explanations in the structural-model approach, which are based on their notions of weak and actual causality. In particular, we give a precise picture of the complexity of deciding explanations, alpha-partial explanations, and partial explanations, and of computing the explanatory power of partial explanations. Moreover, we analyze the complexity of deciding whether an explanation or an alpha-partial explanation over certain variables exists. We also analyze the complexity of deciding explanations and partial explanations in the case of succinctly represented context sets, and the complexity of deciding explanations in the general case of situations. All complexity results are derived for the general case, as well as for the restriction to the case of binary causal models, in which all endogenous variables may take only two values. To our knowledge, no complexity results for explanations in the structural-model approach have been derived so far. Our results give insight into the computational structure of Halpern and Pearl's explanations, and pave the way for efficient algorithms and implementations.</p> |
| first_indexed | 2024-03-07T02:43:01Z |
| format | Conference item |
| id | oxford-uuid:ab1af645-5b57-4060-b32e-311337e047a5 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:43:01Z |
| publishDate | 2002 |
| publisher | Morgan Kaufmann |
| record_format | dspace |
| spelling | oxford-uuid:ab1af645-5b57-4060-b32e-311337e047a52022-03-27T03:19:40ZComplexity Results for Explanations in the Structural−Model ApproachConference itemhttp://purl.org/coar/resource_type/c_5794uuid:ab1af645-5b57-4060-b32e-311337e047a5Department of Computer ScienceMorgan Kaufmann2002Eiter, TLukasiewicz, T<p>We analyze the computational complexity of Halpern and Pearl's (causal) explanations in the structural-model approach, which are based on their notions of weak and actual causality. In particular, we give a precise picture of the complexity of deciding explanations, alpha-partial explanations, and partial explanations, and of computing the explanatory power of partial explanations. Moreover, we analyze the complexity of deciding whether an explanation or an alpha-partial explanation over certain variables exists. We also analyze the complexity of deciding explanations and partial explanations in the case of succinctly represented context sets, and the complexity of deciding explanations in the general case of situations. All complexity results are derived for the general case, as well as for the restriction to the case of binary causal models, in which all endogenous variables may take only two values. To our knowledge, no complexity results for explanations in the structural-model approach have been derived so far. Our results give insight into the computational structure of Halpern and Pearl's explanations, and pave the way for efficient algorithms and implementations.</p> |
| spellingShingle | Eiter, T Lukasiewicz, T Complexity Results for Explanations in the Structural−Model Approach |
| title | Complexity Results for Explanations in the Structural−Model Approach |
| title_full | Complexity Results for Explanations in the Structural−Model Approach |
| title_fullStr | Complexity Results for Explanations in the Structural−Model Approach |
| title_full_unstemmed | Complexity Results for Explanations in the Structural−Model Approach |
| title_short | Complexity Results for Explanations in the Structural−Model Approach |
| title_sort | complexity results for explanations in the structural model approach |
| work_keys_str_mv | AT eitert complexityresultsforexplanationsinthestructuralmodelapproach AT lukasiewiczt complexityresultsforexplanationsinthestructuralmodelapproach |