The orbit problem in higher dimensions

The orbit problem in higher dimensions
复制标题

高维轨道问题

DOI：
10.1145/2488608.2488728
复制
发表时间：
2013
期刊：
ArXiv
影响因子：
--
通讯作者：
J. Worrell
J. Worrell
中科院分区：
--
文献类型：
--
作者：
Ventsislav Chonev;Joël Ouaknine;J. Worrell

文献摘要

被引文献

相似文献

我们考虑Kannan和Lipton轨道问题的高维版本-在重复应用线性变换A的情况下确定目标向量空间V是否可以从起点x到达目标向量空间V。回答Kannan和Lipton在20世纪80年代提出的两个问题，我们证明了当V有一维时，这个问题在多项式时间内可解，当V有二维或三维时，问题在NPRP中。
We consider higher-dimensional versions of Kannan and Lipton's Orbit Problem---determining whether a target vector space V 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 V has dimension one, this problem is solvable in polynomial time, and when V has dimension two or three, the problem is in NPRP.