The complexity of problems related to stochastic modelling and simulation
(A. Bogdanov)

Markov Chains, and more recently Markov random fields, have been used as probabilistic modelling tools in areas including statistical physics, computational biology, and artificial intelligence. Various algorithms have been proposed for (1) simulating the probabilistic process described by the model and (2) reconstructing the model given empirically observed data from the process. We look at these problems from a complexity theoretic perspective and conclude that in several natural settings they are computationally intractable.