Inference Complexity in Continuous Time Bayesian Networks

Liessman Sturlaugson Montana State University, John Sheppard Montana State University
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:324-331, 2014.

Abstract

The continuous time Bayesian network (CTBN) enables temporal reasoning by representing a system as a factored, finite-state Markov process. The CTBN uses a traditional Bayesian network (BN) to specify the initial distribution. Thus, the complexity results of Bayesian networks also apply to CTBNs through this initial distribution. However, the question remains whether propagating the probabilities through time is, by itself, also a hard problem. We show that exact and approximate inference in continuous time Bayesian networks is NP-hard even when the initial states are given.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-university14k, title = {Inference Complexity in Continuous Time {B}ayesian Networks}, author = {University, Liessman Sturlaugson Montana State and University, John Sheppard Montana State}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {324--331}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/university14k/university14k.pdf}, url = {https://proceedings.mlr.press/r12/university14k.html}, abstract = {The continuous time Bayesian network (CTBN) enables temporal reasoning by representing a system as a factored, finite-state Markov process. The CTBN uses a traditional Bayesian network (BN) to specify the initial distribution. Thus, the complexity results of Bayesian networks also apply to CTBNs through this initial distribution. However, the question remains whether propagating the probabilities through time is, by itself, also a hard problem. We show that exact and approximate inference in continuous time Bayesian networks is NP-hard even when the initial states are given.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Inference Complexity in Continuous Time Bayesian Networks %A Liessman Sturlaugson Montana State University %A John Sheppard Montana State University %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-university14k %I PMLR %P 324--331 %U https://proceedings.mlr.press/r12/university14k.html %V R12 %X The continuous time Bayesian network (CTBN) enables temporal reasoning by representing a system as a factored, finite-state Markov process. The CTBN uses a traditional Bayesian network (BN) to specify the initial distribution. Thus, the complexity results of Bayesian networks also apply to CTBNs through this initial distribution. However, the question remains whether propagating the probabilities through time is, by itself, also a hard problem. We show that exact and approximate inference in continuous time Bayesian networks is NP-hard even when the initial states are given. %Z Reissued by PMLR on 04 October 2026.
APA
University, L.S.M.S. & University, J.S.M.S.. (2014). Inference Complexity in Continuous Time Bayesian Networks. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:324-331 Available from https://proceedings.mlr.press/r12/university14k.html. Reissued by PMLR on 04 October 2026.

Related Material