Tl;dr, While an algorithm's computational complexity may be exponential in general (worst-case), it is often possible to stratify its input via some dimension _k_ that makes it polynomial for a fixed _k_, and only exponential in _k_. Conceptually, this quantity captures the core aspect of a problem's structure that makes specific instances of it 'harder' than others, often with intuitive interpretations.

Example: Bayesian Inference and Treewidth

One can easily prove exact inference (decision problem of: "is _P(X)>0_?") is NP-hard by encoding SAT-3 as a Bayes Net. Showing that it's NP is easy too.

Therefore, inference is NP-complete, implying that algorithms are worst-case exponential. But this can't be the typical case! Let's examine the example of a Bayes Net whose structure is a chain [...]

---

Outline:

(00:32) Example: Bayesian Inference and Treewidth

(04:13) General Lesson

The original text contained 4 footnotes which were omitted from this narration.

---

First published:

Source:

Narrated by TYPE III AUDIO.