Inference complexity in continuous time Bayesian networks
Liessman E. Sturlaugson, John W. Sheppard · 2014
The continuous time Bayesian network (CTBN) enables temporal reasoning by rep-resenting a system as a factored, finite-state Markov process. The CTBN uses a tra-ditional Bayesian network (BN) to specify the initial distribution. Thus, the complex-ity results of Bayesian networks also apply to CTBNs through this initial distribution. However, the question remains whether prop-agating the probabilities through time is, by itself, also a hard problem. We show that exact and approximate inference in continu-ous time Bayesian networks is NP-hard even when the initial states are given. 1