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

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

• •建立了关于连通性问题的纯动态规划复杂度的下界。
• •表明代数技术对于实现最佳性能是必要的。
• •使用热带电路来模拟纯动态规划算法。
• •将热带电路复杂度与非确定性通信复杂度联系起来。