On the Computational Complexity of Limit Cycles in Dynamical Systems
On the Computational Complexity of Limit Cycles in Dynamical Systems
复制标题
论动力系统极限环的计算复杂性
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Nisheeth K. Vishnoi
中科院分区：
文献类型：
--
作者：
C. Papadimitriou;Nisheeth K. Vishnoi
我们从计算的角度研究了紧凑型域中的二维连续动力系统的繁殖 - 弯曲定理，从而寻求算法来找到该经典结果所承诺的限制周期。我们首先考虑对该定理的离散类似物，并表明两者都在限制周期中找到一个点，又确定给定点是否在一个点上，都是pspace complete。对于连续版本，我们表明这两个问题在实际复杂性意义上都是无法兼容的。即，它们的复杂性任意高。随后，我们引入了一个近似循环的概念，并证明了近似的Poincare-Bendixson定理，确保某些轨道在没有近似固定点的情况下非常接近形成周期。令人惊讶的是，它适用于所有维度。根据算术电路定义的相应计算问题是PSPACE完整的。
We study the Poincare-Bendixson theorem for two-dimensional continuous dynamical systems in compact domains from the point of view of computation, seeking algorithms for finding the limit cycle promised by this classical result. We start by considering a discrete analogue of this theorem and show that both finding a point on a limit cycle, and determining if a given point is on one, are PSPACE-complete. For the continuous version, we show that both problems are uncomputable in the real complexity sense; i.e., their complexity is arbitrarily high. Subsequently, we introduce a notion of an approximate cycle and prove an approximate Poincare-Bendixson theorem guaranteeing that some orbits come very close to forming a cycle in the absence of approximate fixpoints; surprisingly, it holds for all dimensions. The corresponding computational problem defined in terms of arithmetic circuits is PSPACE-complete.