In a previous post I mentioned a very simple algorithm for solving decision problems encoded as sheaves on inputs that display some recursive structure. In this post I’ll talk about what goes wrong with that approach when we’re trying to compute on inputs that are presented in a recursive, tree-like way and I’ll also propose a route for circumnavigation. But first let’s review what I mean by “recursive structure”.
This is a companion discussion topic for the original entry at https://bmbumpus.com/2022/12/05/dynamic-programming-on-non-recursive-structures/