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 <span>_k_</span> that makes it polynomial for a fixed <span>_k_</span>, and only exponential in <span>_k_</span>. 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 <span>_P(X)>0_</span>?") is NP-hard by encoding SAT-3 as a Bayes Net. Showing that it's NP is easy too.

Given a 3-SAT instance <span>_phi_</span> over <span>_Q_1, dots Q_n_</span>, one can cleverly encode it as a Bayes Net <span>_B_{phi}_</span> such that <span>_P_{B_{phi}}(X=x^1) > 0_</span> if and only if <span>_phi_</span> is satisfiable (From Koller & Friedman 2009).

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:
July 3rd, 2024

Source:
https://www.lesswrong.com/posts/Ja9NP3NJpEd7BXMnW/when-are-results-from-computational-complexity-not-too

---

Narrated by TYPE III AUDIO.

“When Are Results from Computational Complexity Not Too Coarse?” by Dalcy

LessWrong (30+ Karma)