Limits of dynamic programming

点击翻译按钮获取中文摘要

Our current knowledge of the dynamic programming complexity (DP complexity) of algorithmic problems is very disappointing, since the all-pairs shortest path problem is one of only few nontrivial algorithmic problems whose DP complexity is reasonably understood. The DP complexity of other shortest path problems remains unresolved as well the alleged optimality of the many fundamental dynamic programming algorithms in computer science and bioinformatics. We encounter the same bleak situation when approximating with dynamic programming algorithms.Our goal is to formulate adequate models capturing the paradigm of dynamic programming, and to prove lower bounds for important optimization problems in these models. In particular, powerful methods from boolean circuitcomplexity and communication complexity are to be modified to work also fordynamic programming algorithms.