Abstract: Probabilistic inference in graphical model is to compute the partition function, the marginal probability distri- bution,and the conditional probability distribution through summing variables of the joint probability distribution. The hardness and inapproximability of the probabilistic inference arc important problem, and arc the foundation to design the probabilistic inference algorithm and approximate probabilistic inference algorithm. We analyied the computational com- plexity of the exact probabilistic inference and approximate probabilistic inference. In particular, we constructed a coun- ting reduction from the#2SAT problem to the probabilistic inference problem in polynomial time,and proved that the problem of computing the partition function, marginal probability distribution and conditional probability distribution in a Ising graphical model is#P-hard. Moreover, approximating the probability distribution is NP-hard.

Key words: Ising graphical model, Probabilistic inference, Computational complexity, Hardness, Inapproximability