computational complexity of graphical model inference

(40 minutes to learn)


The major inference problems for graphical models (marginalization, MAP assignment, and partition function) are all intractable in the worst case. In particular, marginalization and partition function computation are both #P-complete, and MAP inference is NP-complete.


This concept has the prerequisites:

Core resources (read/watch one of the following)


See also