On the Complexity of the Orbit Problem
On the Complexity of the Orbit Problem
复制标题
论轨道问题的复杂性
作者：
Ventsislav Chonev;Joël Ouaknine;J. Worrell
我们考虑 Kannan 和 Lipton 轨道问题的高维版本 - 确定在重复应用线性变换 A 的情况下，是否可以从起点 x 到达目标向量空间 ν。回答 Kannan 和 Lipton 在 20 世纪 80 年代提出的两个问题，我们表明，当 ν 具有一维时，该问题可在多项式时间内解决，而当 ν 具有二维或三维时，该问题属于 NPRP。
We consider higher-dimensional versions of Kannan and Lipton’s Orbit Problem—determining whether a target vector space ν may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by Kannan and Lipton in the 1980s, we show that when ν has dimension one, this problem is solvable in polynomial time, and when ν has dimension two or three, the problem is in NPRP.
多面体撞击问题
DOI：
10.1137/1.9781611973730.64
发表时间：
2015
期刊：
--
影响因子：
--
作者：
Chonev V
通讯作者：
Chonev V