Minimal Reachability is Hard To Approximate
Minimal Reachability is Hard To Approximate
复制标题
最小可达性很难近似
DOI：
10.1109/tac.2018.2836021
复制
发表时间：
2017
影响因子：
6.8
通讯作者：
Vasileios Tzoumas
中科院分区：
文献类型：
--
作者：
A. Jadbabaie;Alexander Olshevsky;George Pappas;Vasileios Tzoumas
在本说明中，我们考虑了选择的问题，该问题应启动线性动力学系统的哪些节点，以使状态从系统的初始条件转移到给定的最终状态。假设有标准的复杂性假设，我们表明该问题在多项式甚至准多项式时间中都无法有效地解决或近似。
In this note, we consider the problem of choosing, which nodes of a linear dynamical system should be actuated so that the state transfer from the system's initial condition to a given final state is possible. Assuming a standard complexity hypothesis, we show that this problem cannot be efficiently solved or approximated in polynomial, or even quasi-polynomial, time.