Reference: Cooper, G. & Herskovits, E. Determination of the Entropy of a Belief Network is NP-Hard. KSL, June, 1991.
Abstract: In this paper, we analyze the computational complexity of determining the entropy of an arbitrary probability distribution represented by a belief network, and show that this task is NP-hard in the number of nodes in the network. This analysis is similar to the analysis of the computational complexity of inference using belief networks.