The Large N Limit of Dynamic Programming is a Greedy Algorithm

Combinatorial optimization, concerned with finding optima across a discrete state space, often admits at least two types of solutions. A dynamic programming approach that uses a problem’s recursive substructure to build a final solution, and a greedy approach that approximates a global optimum by taking locally optimal steps. These two approaches are typically seen as distinct and unrelated, defined by different implementations and computational complexities. However, the two can be connected by stepping into a different discipline.

By converting combinatorial optimization problems into physical systems, we derive partition functions that reflect the recursive nature of dynamic programming and approximations that reproduce greedy solutions to the original problem. Ultimately, we show that the large N limit of dynamic programming results in a greedy algorithm. We apply this procedure to common combinatorial optimization problems, including the Knapsack Problem, the Coin-Change Problem, and the Number Partitioning Problem. We then discuss limitations to its extension to more complex problems like the Traveling Salesperson Problem. We conclude by widening the problem scope and discussing how the computational complexity of various algorithms is manifest in the statistical physics representations of these algorithms and, thus, how physics can serve as a bridge connecting differenent algorithms in the solution space of optimization problems.