IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING?
From MaRDI portal
Publication:6131225
Abstract: Many tasks in statistical and causal inference can be construed as problems of emph{entailment} in a suitable formal language. We ask whether those problems are more difficult, from a computational perspective, for emph{causal} probabilistic languages than for pure probabilistic (or "associational") languages. Despite several senses in which causal reasoning is indeed more complex -- both expressively and inferentially -- we show that causal entailment (or satisfiability) problems can be systematically and robustly reduced to purely probabilistic problems. Thus there is no jump in computational complexity. Along the way we answer several open problems concerning the complexity of well known probability logics, in particular demonstrating the -completeness of a polynomial probability calculus, as well as a seemingly much simpler system, the logic of comparative conditional probability.
Cites work
- scientific article; zbMATH DE number 1169378 (Why is no real title available?)
- scientific article; zbMATH DE number 1467490 (Why is no real title available?)
- scientific article; zbMATH DE number 3321248 (Why is no real title available?)
- A logic for reasoning about probabilities
- Absolutely no free lunches!
- Causal diagrams for empirical research
- Causality. Models, reasoning, and inference
- Complexity of some geometric and topological problems
- Complexity results for structure-based causality.
- Controversies in the Foundations of Statistics
- Decidability and expressiveness for first-order logics of probability
- Dynamic interactive epistemology
- Frequentist probability and frequentist statistics
- On Pearl’s Hierarchy and the Foundations of Causal Inference
- On the Numerical Representation of Qualitative Conditional Probability
- On the hardness of approximate reasoning
- Philosophy and the practice of Bayesian statistics
- Probabilistic Inference and Influence Diagrams
- Probability logic for type spaces
- Probability logics. Probability-based formalization of uncertain reasoning
- Quantifying over events in probability logic: an introduction
- Survey of polynomial transformations between NP-complete problems
- The art gallery problem is \(\exists \mathbb{R}\)-complete
- The complexity of reasoning about knowledge and time. I: Lower bounds
- The complexity of theorem-proving procedures
- The computational complexity of structure-based causality
- Thirty Essays on Geometric Graph Theory
- Understanding machine learning. From theory to algorithms
- When are probabilistic explanations possible?
This page was built for publication: IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131225)
