A note on the complexity of the causal ordering problem

DOI10.1016/J.ARTINT.2016.06.004zbMATH Open1385.68017arXiv1508.05804OpenAlexW2196798331MaRDI QIDQ309924FDOQ309924

Authors: Bernardo Gonçalves, Fabio Porto 

Publication date: 7 September 2016

Published in: Artificial Intelligence (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Introduction to algorithms.
• Title not available (Why is that?)
• Causality and model abstraction
• Causal approximations
• Graph theory with applications
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Automated modelling of physical systems
• A note on the correctness of the causal ordering algorithm
• On bipartite and multipartite clique problems
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• 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)