---
title: "Complexity Results for Structure-Based Causality"
authors:
  - "Thomas Eiter"
  - "Thomas Lukasiewicz"
doi: ""
url: "https://ijcai.org/proceedings/2001/5"
pdf: "https://ijcai.org/proceedings/2001/0005.pdf"
venue: "Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence"
year: 2001
pages: "35-41"
track: ""
keywords:
---

# Complexity Results for Structure-Based Causality

Thomas Eiter, Thomas Lukasiewicz

*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.