information
Decode the hidden path
It is the 1960s, and signals arrive down a noisy channel as garbled observations of a hidden sequence of states — the true message you must recover. Brute force is hopeless: the number of possible state sequences explodes exponentially with the length of the message. Recover the single most likely hidden path efficiently and exactly, exploiting the chain's structure so that dynamic programming collapses the exponential search into a single linear pass. Exactness with efficiency is the prize. Get it wrong and either you decode in exponential time no real receiver can afford, or you settle for an approximate path that misreads the message — this algorithm became the workhorse of digital communication and speech, wherever a clean sequence must be pulled out of noise.
Who this problem belongs to
The two figures whose methods fit it best, out of 33 in contention.
This is literally his algorithm. In his 1967 IEEE Transactions on Information Theory paper, Viterbi introduced maximum-likelihood decoding of convolutional codes by organizing the hidden state sequence as a trellis, propagating path metrics forward, and keeping only the surviving best path into each state — exactly the dynamic-programming collapse the problem demands, exact and linear in message length. He conceived it, characteristically, as a pedagogical simplification of sequential decoding, and Forney later showed it was optimal maximum-likelihood sequence estimation. He then co-founded Qualcomm and pushed the algorithm into real receivers, making it the workhorse of digital communication the problem describes. Every element — the noisy channel, the Markov state structure, exactness with efficiency — is the setting he built the method for. No carrier in this batch is closer.
Bellman formalized dynamic programming at RAND in the early 1950s, and his principle of optimality is precisely the mechanism this problem asks you to exploit: the best path to any state at time t must extend a best path to some state at time t-1, so exponential enumeration collapses into a linear forward pass over states. The Viterbi algorithm is, structurally, Bellman's recursion applied to a probabilistic trellis with log-likelihood costs — Viterbi himself worked in a field saturated with Bellman's ideas. Bellman also named the curse of dimensionality, so he understood exactly when the state space stays tractable. What he lacked was the communications framing: convolutional codes, channel models, and hidden Markov observation structure were not his domain. The engine is his; the application is Viterbi's.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
33 figures are scored on this problem. Draw it in a battle to see where you land.