Complexity Results for Structure-Based Causality

Eiter, Thomas; Lukasiewicz, Thomas

Complexity Results for Structure-Based Causality

Download BibTeX Cite

Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 35-41.

Abstract

We analyze the computational complexity of causal relationships in Pearl’s structural models, where we focus on causality between variables, event causality, and probabilistic causality. In particular, we analyze the complexity of the sophisticated notions of weak and actual causality by Halpern and Pearl. In the course of this, we also prove an open conjecture by Halpern and Pearl, and establish other semantic results. To our knowledge, no complexity aspects of causal relationships have been considered so far, and our results shed light on this issue.

Thomas Eiter, and Thomas Lukasiewicz. 2001. Complexity Results for Structure-Based Causality. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01. IJCAI, 35–41. https://ijcai.org/proceedings/2001/5

@inproceedings{ijcai2001p5,
  title     = {Complexity Results for Structure-Based Causality},
  author    = {Eiter, Thomas and Lukasiewicz, Thomas},
  booktitle = {Proceedings of the Seventeenth International Joint Conference on
               Artificial Intelligence, {IJCAI-01}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  pages     = {35--41},
  year      = {2001},
  url       = {https://ijcai.org/proceedings/2001/5},
}

TY  - CPAPER
TI  - Complexity Results for Structure-Based Causality
AU  - Eiter, Thomas
AU  - Lukasiewicz, Thomas
T2  - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2001
SP  - 35
EP  - 41
UR  - https://ijcai.org/proceedings/2001/5
ER  -