Approximation limits of dynamic programming

动态规划（DP）是一个成功的算法范例，用于解决优化，计数和决策问题。 精确动态规划算法的局限性目前已经得到了比较好的理解：我们能够证明必要操作数量的下限。 然而，关于动态规划算法的近似能力的知识状态仍然相当令人沮丧：近似DP算法的非平凡下限是已知的。在拨款期间，我们已经关闭了这个知识差距：我们已经证明了第一，甚至指数下界也近似DP算法。我们还证明了随机化并不能显著地提高DP算法的速度，我们的下界对于在递归方程中使用基本（min，+）或（max，+）运算的所谓纯DP算法是成立的。目前的结果是，也要感谢我们的一个新结果，减法运算可以指数级地加速DP算法。继续这个项目的目标是了解动态规划中减法令人惊讶的力量的原因。我们将通过证明带减法的DP算法的下界来实现这一点。

Dynamic programming (DP) is a successful algorithmic paradigm for the solution of optimization, counting and decision problems. The limits of exact dynamic programming algorithms are currently relatively well understood: we are able to prove lower bounds on the number of necessary operations. The state of knowledge about the approximation power of dynamic programming algorithms, however, remained rather frustrating: no non-trivial lower bounds for approximating DP algorithms were known. During the appropriation period, we have closed this knowledge gap: we have proved the first, even exponential lower bounds also for approximating DP algorithms. We have also shown that randomization cannot substantially speed up DP algorithms.Our lower bounds hold for so-called pure DP algorithms using the basic (min,+) or (max,+) operations in their recursion equations. It turned currently out, also thanks to one of our new results, that the subtraction operation can exponentially speed up DP algorithms. The goal of the continuation of the project is to understand the reason for this surprising power of subtraction in dynamic programming. We are going to achieve this by proving lower bounds for DP algorithms with subtraction.