Reasoning Under Uncertainty

A patient reports a fever. The doctor doesn't know the cause — but updates a hunch: flu just got more likely. Add a sneeze, and an allergy climbs the list while flu may drop. We do this constantly: take evidence, revise our beliefs about hidden causes.

Written down, this is a Bayesian network: a web of variables — diseases, symptoms, risk factors — wired by how they influence one another, each with the probabilities that connect them. Inference means asking, given some observed evidence, what's the updated (posterior) probability of the things we can't see?

For one or two variables it's just Bayes' rule. But real networks have hundreds of interlinked variables, and the honest way to compute an exact answer is to sum over every combination of the unknowns — a combinatorial explosion. That's why exact Bayesian inference is, formally, #P-hard — a class believed even harder than NP.

Try it. This little network has two hidden causes — Flu and Allergy — and three symptoms they influence: Fever, Sneeze and Fatigue. Click a symptom to set it present, absent, or unknown. The bars show the updated probability of each cause given your evidence.

<p class="hint">{{hint}}</p>
<div class="symptoms" id="symptoms"></div>
<div class="causes" id="causes"></div>
<button id="reset" type="button" class="ghost">{{clear_btn}}</button>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.symptoms { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: 1rem; }
.sym { border: 2px solid #cdd9e2; border-radius: 10px; padding: .55rem .8rem; cursor: pointer; font: 700 14px system-ui; color: #1d3557; background: #fff; min-width: 110px; text-align: center; }
.sym small { display: block; font-weight: 600; font-size: .82em; margin-top: .15rem; }
.sym.present { border-color: #c0392b; background: #fdecea; color: #c0392b; }
.sym.absent { border-color: #457b9d; background: #eef3f7; color: #457b9d; }
.causes { display: flex; flex-direction: column; gap: .7rem; margin-bottom: 1rem; }
.cause { }
.cause .lab { font: 700 14px system-ui; color: #1d3557; margin-bottom: .25rem; display: flex; justify-content: space-between; }
.bar { height: 22px; background: #eef1f4; border-radius: 6px; overflow: hidden; position: relative; }
.fill { height: 100%; background: linear-gradient(90deg,#2a9d8f,#457b9d); transition: width .35s; }
.prior { position: absolute; top: 0; bottom: 0; width: 2px; background: #c0392b; }
.priorlbl { font: 600 10px system-ui; color: #c0392b; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

Watch for explaining-away: turn on Fatigue and both causes rise. Now add Sneeze — the allergy explanation surges and flu falls back, because the fatigue is now accounted for. That subtle interaction between causes is exactly what makes inference rich, and hard.

Inference is hard in a deeper way than most problems here:

• The naive method sums over everything. With n unknown binary variables there are $2^{n}$ combinations to add up — exponential.
• Exact inference is #P-hard. It's a counting problem (summing probabilities), and the counting class #P is believed even harder than NP — you're not just finding one answer, you're effectively tallying exponentially many.
• Approximation is hard too. Getting a guaranteed-close answer is itself NP-hard in general, so there's no universal easy shortcut.
• Structure can rescue you. If the network is sparse and tree-like (low treewidth), exact algorithms like variable elimination and the junction tree run efficiently. The trouble is dense, loopy networks.
• Practice approximates. Real systems use MCMC (random sampling, e.g. Gibbs), variational inference (fit a simpler distribution) and belief propagation (pass messages between variables) — fast and usually excellent, without exactness guarantees.

So Bayesian inference is hardness of a different flavor: not "find the needle," but "weigh the whole haystack."

Reasoning under uncertainty is everywhere decisions meet incomplete information:

• Medical diagnosis: weighing symptoms, tests and history to rank possible conditions.
• Spam filtering: classic naive-Bayes filters weigh words to judge "spam or not."
• Risk and reliability: fault trees and safety analysis in engineering and finance.
• Robotics and tracking: estimating hidden state (position, intent) from noisy sensors.
• Modern AI: probabilistic models, and the Bayesian view that underlies much of machine learning.

Because exact answers are out of reach at scale, these systems lean on the approximate-inference toolbox — fast methods that are right far more often than theory guarantees.

Bayesian inference is the math of changing your mind well. Each piece of evidence ripples through a web of causes, nudging probabilities up and down — sometimes in surprising ways, like one symptom explaining away another. It's how doctors, filters and robots reason when they can't be certain.

Its hardness is a different shade from the rest of this site: not the search for one elusive answer, but the counting of exponentially many possibilities — the realm of #P. And as everywhere, the response is ingenious approximation: sample, simplify, pass messages. We can't always compute the exact probability, but we've learned to estimate it well enough to trust our diagnoses, our filters, and our machines.