I was wondering if someone knew why computing the partition function for probabilistic graphical models is NP-Hard?
I would like to see a full blown rigorous proof, however, I am as happy to get a link to it too (I expect this to be a well known result, so a link to the proof of the result would not surprise me too much). I did try googling it and could not find where its proven rigorously and completely. I also tried searching through Koller's book on PGM (probabilistic graphical models)
If you instead have an intuitive argument, you are also welcome to post it (however, I also want to see why its NP-Hard in a precise way).
These are my thoughts and why its not clear to me why its NP-complete. For me it seems that computing such a normalizing constant should be strictly exponential in general (note I said exponential and NOT NP-complete). What I mean is that, for example, consider the problem of counting to N. The input size is $2^k$ where k is the number of bits to specify N. Its clear that this problem is always exponential and not NP-complete. For me, this problem of normalizing, unless the graph has a very nice and special factorization, I cannot see why it should not be a inherently exponential task (i.e. worse than NP-complete, since we are sure there are no feasible algorithms to compute it exactly).
Not sure what the community thinks about that but it would be cool to clarify that misconception. I guess the misconception might be clarified once I see a reduction to an NP-complete problem (which makes me sad because it means my intuition that its strictly exponential was wrong).
As a reference this is what I mean as a partition function.
Let $P_{\phi}$ be a Gibbs distribution parametrized by a set of factors $\phi = \{ \phi_1(D_1), ... \phi_{k}(D_k)\}$
$$P_{\phi}(X_1, ..., X_n) = \frac{1}{Z} \tilde{P}_{\phi}(X_1, ..., X_N)$$
where $\tilde{P}_{\phi}$ is the unormalized probability measure and Z is the partition function that normalizes it:
$$Z = \sum_{X_1, ..., X_N} \tilde{P}_{\phi}(X_1, ...,X_n)$$
As a second reference, click here to learn about PGMs
It is actually harder than that. It is #p-complete. For proof see this: http://www.math.washington.edu/~billey/colombia/references/valiant.permanent.1979pdf.pdf
Also see these: http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete http://en.wikipedia.org/wiki/Computing_the_permanent