Complexity results for structure-based causality. (Q1852862)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Complexity results for structure-based causality.
scientific article

    Statements

    Complexity results for structure-based causality. (English)
    0 references
    0 references
    0 references
    21 January 2003
    0 references
    We give a precise picture of the computational complexity of causal relationships in Pearl's structural models, where we focus on causality between variables, event causality, and probabilistic causality. As for causality between variables, we consider the notions of causal irrelevance, cause, cause in a context, direct cause, and indirect cause. As for event causality, we analyze the complexity of the notions of necessary and possible cause, and of the sophisticated notions of weak and actual cause by Halpern and Pearl. In the course of this, we also prove an open conjecture by Halpern and Pearl, and establish other semantic results. We then analyze the complexity of the probabilistic notions of probabilistic causal irrelevance, likely causes of events, and occurrences of events despite other events. Moreover, we consider decision and optimization problems involving counterfactual formulas. To our knowledge, no complexity aspects of causal relationships in the structural-model approach have been considered so far, and our results shed light on this issue.
    0 references
    Causal model
    0 references
    Probabilistic causal model
    0 references
    Causality between variables
    0 references
    Event causality
    0 references
    Probabilistic causality
    0 references
    Weak cause
    0 references
    Actual cause
    0 references
    Complexity
    0 references
    Counting hierarchy
    0 references

    Identifiers