On the complexity of the orbit problem
Chonev VK, Ouaknine J, Worrell J. 2016. On the complexity of the orbit problem. Journal of the ACM. 63(3), 23.
Download (ext.)
DOI
Journal Article
| Published
| English
Scopus indexed
Author
Chonev, Ventsislav KISTA;
Ouaknine, Joël;
Worrell, James
Department
Abstract
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.
Publishing Year
Date Published
2016-06-01
Journal Title
Journal of the ACM
Volume
63
Issue
3
Article Number
23
IST-REx-ID
Cite this
Chonev VK, Ouaknine J, Worrell J. On the complexity of the orbit problem. Journal of the ACM. 2016;63(3). doi:10.1145/2857050
Chonev, V. K., Ouaknine, J., & Worrell, J. (2016). On the complexity of the orbit problem. Journal of the ACM. ACM. https://doi.org/10.1145/2857050
Chonev, Ventsislav K, Joël Ouaknine, and James Worrell. “On the Complexity of the Orbit Problem.” Journal of the ACM. ACM, 2016. https://doi.org/10.1145/2857050.
V. K. Chonev, J. Ouaknine, and J. Worrell, “On the complexity of the orbit problem,” Journal of the ACM, vol. 63, no. 3. ACM, 2016.
Chonev VK, Ouaknine J, Worrell J. 2016. On the complexity of the orbit problem. Journal of the ACM. 63(3), 23.
Chonev, Ventsislav K., et al. “On the Complexity of the Orbit Problem.” Journal of the ACM, vol. 63, no. 3, 23, ACM, 2016, doi:10.1145/2857050.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar