A note on the complexity of the causal ordering problem

DOI10.1016/J.ARTINT.2016.06.004MaRDI QIDQ309924zbMATH OpenOpenAlexFDO

Authors Bernardo Gonçalves, Fabio Porto

Publication date 7 September 2016

Published in Artificial Intelligence (Search for Journal in Brave)

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

zbMATH Keywords

causal orderingcausal reasoninghypothesis managementstructural equations

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: In this note we provide a concise report on the complexity of the causal ordering problem, originally introduced by Simon to reason about causal dependencies implicit in systems of mathematical equations. We show that Simon's classical algorithm to infer causal ordering is NP-Hard---an intractability previously guessed but never proven. We present then a detailed account based on Nayak's suggested algorithmic solution (the best available), which is dominated by computing transitive closure---bounded in time by $O(|mathcalV|cdot|mathcalS|)$, where $mathcalS(mathcalE,mathcalV)$ is the input system structure composed of a set $mathcalE$ of equations over a set $mathcalV$ of variables with number of variable appearances (density) $|mathcalS|$. We also comment on the potential of causal ordering for emerging applications in large-scale hypothesis management and analytics.

Recommendations

• A note on the correctness of the causal ordering algorithm
• Complexity results for structure-based causality.
• scientific article; zbMATH DE number 3843452
• scientific article; zbMATH DE number 67865
• Complexity results for explanations in the structural-model approach

Cites work

• scientific article; zbMATH DE number 1493045 (Why is no real title available?)
• scientific article; zbMATH DE number 3085485 (Why is no real title available?)
• A note on the correctness of the causal ordering algorithm
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Automated modelling of physical systems
• Causal approximations
• Causality and model abstraction
• Graph theory with applications
• Introduction to algorithms.
• On bipartite and multipartite clique problems

Cited in

(5)

• AUTOMATIC INFERENCE OF THE CONTEMPORANEOUS CAUSAL ORDER OF A SYSTEM OF EQUATIONS
• Emerging order in CAS theory: mapping some perspectives
• Similarity Orders from Causal Equations
• scientific article; zbMATH DE number 3843452 (Why is no real title available?)
• A note on the correctness of the causal ordering algorithm

This page was built for publication: A note on the complexity of the causal ordering problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q309924)