IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING?

DOI10.1017/S1755020322000211arXiv2111.13936OpenAlexW3217313098MaRDI QIDQ6131225FDOQ6131225

Authors: Thomas F. III Icard 

Publication date: 4 April 2024

Published in: The Review of Symbolic Logic (Search for Journal in Brave)

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 $existsmathbbR$-completeness of a polynomial probability calculus, as well as a seemingly much simpler system, the logic of comparative conditional probability.

Full work available at URL: https://arxiv.org/abs/2111.13936

zbMATH Keywords

complexityprobabilitylogiccausationETR

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Philosophical and critical aspects of logic and foundations (03A05)

Cites Work

• Philosophy and the practice of Bayesian statistics
• Causality. Models, reasoning, and inference
• Understanding machine learning. From theory to algorithms
• Causal diagrams for empirical research
• The complexity of theorem-proving procedures
• When are probabilistic explanations possible?
• On the hardness of approximate reasoning
• Probability logic for type spaces
• A logic for reasoning about probabilities
• Frequentist probability and frequentist statistics
• Probabilistic Inference and Influence Diagrams
• Complexity of some geometric and topological problems
• Decidability and expressiveness for first-order logics of probability
• Probability logics. Probability-based formalization of uncertain reasoning
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dynamic interactive epistemology
• Complexity results for structure-based causality.
• The complexity of reasoning about knowledge and time. I: Lower bounds
• On Pearl’s Hierarchy and the Foundations of Causal Inference
• Title not available (Why is that?)
• Survey of polynomial transformations between NP-complete problems
• Controversies in the Foundations of Statistics
• On the Numerical Representation of Qualitative Conditional Probability
• The computational complexity of structure-based causality
• Thirty Essays on Geometric Graph Theory
• The art gallery problem is \(\exists \mathbb{R}\)-complete
• Quantifying over events in probability logic: an introduction
• Absolutely no free lunches!

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)