computational complexity of graphical model inference

(40 minutes to learn)

Summary

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.

Context

This concept has the prerequisites:

Core resources (read/watch one of the following)

-Paid-

See also