# 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-

→ Probabilistic Graphical Models: Principles and Techniques

A very comprehensive textbook for a graduate-level course on probabilistic AI.

Location:
Section 9.1, pages 288-292

## See also

- When exact inference is infeasible, we must resort to approximate inference algorithms, such as:
- loopy belief propagation , which applies the BP update rules on non-tree graphs
- Markov chain Monte Carlo , a sampling-based method
- variational inference , which tries to find a tractable approximation to the posterior