论文标题
动态系统理论和NP硬性问题的算法
Dynamical Systems Theory and Algorithms for NP-hard Problems
论文作者
论文摘要
本文在动态系统理论和算法的交集中调查了新兴问题的新兴区域。传统上，在计算机科学和离散优化的权限下，计算复杂性和非确定性多项式时间（NP）问题的分析已落在。但是，在过去的几年中，动态系统理论越来越多地用于构建新算法并阐明问题实例的硬度。我们调查了一系列示例，这些示例说明了在计算复杂性分析和新颖算法构建的背景下使用动态系统理论的范围。 In particular, we summarize a) a novel approach for clustering graphs using the wave equation partial differential equation, b) invariant manifold computations for the traveling salesman problem, c) novel approaches for building quantum networks of Duffing oscillators to solve the MAX-CUT problem, d) applications of the Koopman operator for analyzing optimization algorithms, and e) the use of dynamical systems theory to analyze computational complexity.
This article surveys the burgeoning area at the intersection of dynamical systems theory and algorithms for NP-hard problems. Traditionally, computational complexity and the analysis of non-deterministic polynomial-time (NP)-hard problems have fallen under the purview of computer science and discrete optimization. However, over the past few years, dynamical systems theory has increasingly been used to construct new algorithms and shed light on the hardness of problem instances. We survey a range of examples that illustrate the use of dynamical systems theory in the context of computational complexity analysis and novel algorithm construction. In particular, we summarize a) a novel approach for clustering graphs using the wave equation partial differential equation, b) invariant manifold computations for the traveling salesman problem, c) novel approaches for building quantum networks of Duffing oscillators to solve the MAX-CUT problem, d) applications of the Koopman operator for analyzing optimization algorithms, and e) the use of dynamical systems theory to analyze computational complexity.
