Why doesn't memoization turn every exponential recursion into a polynomial algorithm?

## The claim being corrected "Any exponential recursion can be memoized into polynomial time" is one of the most confidently stated wrong answers in this area. It survives because the examples people learn on — a numeric recurrence, a two-index sequence problem — happen to have small state spaces, so the cache really does collapse the work. The collapse is a property of those problems, not of caching. ## The formula that settles it For a memoized recursion: ``` time ~= (number of distinct reachable states) x (work per state, excluding recursive calls) space ~= (number of distinct stored states) + (recursion depth) ``` A cache guarantees each distinct state is evaluated once. That is its entire contribution. It says nothing about how many distinct states exist — and that count is fixed by how you identify a subproblem, which is fixed by what the answer actually depends on. For the numeric case where a subproblem is named by a single integer up to `n`, there are about `n` states, each doing constant work, so a call tree that blew up becomes linear. Nothing mysterious happened: the state space was always small, and the cache simply stopped the recursion from asking the same small set of questions repeatedly. ## The case where it does not collapse Consider searching a road network for the highest-value route from a start to a destination that never revisits a place. Whether a continuation is legal depends on which places have already been used, so the subproblem must be identified by both: ``` BEST(u, target, visited): if u == target: return 0 best = -INFINITY for v in neighbors(u): if v not in visited: best = max(best, w(u, v) + BEST(v, target, visited + {v})) return best // memo key must be the pair (u, visited) -- not u alone ``` Now count states. The first component ranges over places; the second ranges over *subsets* of places. The product grows exponentially with the number of places. Memoizing is not wrong — the cache does earn hits, because the same `(place, visited set)` pair is genuinely reachable by different orderings of the same set — but one evaluation per distinct state is still exponentially many evaluations, and the table itself needs exponential memory, which usually becomes the binding constraint long before the clock does. This is why the subproblem space, not the recursion, determines the complexity class. Memoization is a technique for eliminating *redundancy*; it cannot eliminate *distinct required work*. ## The quieter failure: shrinking the key Facing an unaffordable table, the tempting move is to drop part of the key — memoize on the current place alone. The state space becomes small and the algorithm becomes fast, and it also becomes incorrect. Caching is only valid when the stored answer is a **function of the key**: the same key must always imply the same answer. The best continuation from a place depends on which places remain available, so two visits with different visited sets have different answers under one key. The cache serves the first one to both. This bug is nastier than a slow algorithm because it does not announce itself. Small test graphs often have few enough alternative routes that the wrong cached answer coincides with the right one; the discrepancy appears on larger inputs, intermittently, and looks like a data problem rather than a design error. When reviewing a memoized recursion, the check is mechanical: **list everything the returned value depends on, and confirm every one of those things appears in the key.** ## What to do instead - **Size the state space first.** Multiply out the ranges of the parameters before writing a line. If the product is exponential, memoizing is not the fix and no amount of tuning will make it one. - **Look for state you can legitimately drop.** Sometimes a parameter is redundant — derivable from the others, or provably irrelevant to the answer. Dropping such a parameter is sound and shrinks the space genuinely; dropping a parameter the answer depends on is the bug above. - **Accept exponential deliberately when the input is bounded.** A subset-indexed table is a real and respectable technique when the element count is small and fixed; the decision is a capacity decision, made with the ceiling written down. - **Change the problem.** Approximation, a heuristic search with pruning, or a reformulation that removes the global constraint are the usual routes once the exact state space is known to be unaffordable. ## The one-line version Memoization bounds work by the size of the subproblem space. Polynomial time follows only when that space is polynomial — and when it is not, the choice is an exponential cost you accepted knowingly or a cache key that lies.