关于连通性问题的动态规划的下界

本文为具有有界路径宽度的图上的连通性问题（如旅行商问题）的纯动态规划算法（由热带电路建模）提供了复杂度的下界。结果表明，代数技术对于实现最佳性能至关重要，因为纯动态规划方法面临着严重的限制。本文的贡献在于确立了这些限制，并为在设计这些问题的有效算法时代数方法的必要性提供了证据。