Journal article
On the complexity of the orbit problem
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 395.1KB, Terms of use)
-
- Publisher copy:
- 10.1145/2857050
Authors
- Publisher:
- Association for Computing Machinery
- Journal:
- Journal of the ACM More from this journal
- Volume:
- 63
- Issue:
- 3
- Article number:
- 23
- Publication date:
- 2016-06-22
- Acceptance date:
- 2015-12-01
- DOI:
- EISSN:
-
1557-735X
- ISSN:
-
0004-5411
- Language:
-
English
- Keywords:
- Pubs id:
-
pubs:518720
- UUID:
-
uuid:a9ff7ec8-83ed-427c-8c5d-fb5012b2bc9b
- Local pid:
-
pubs:518720
- Source identifiers:
-
518720
- Deposit date:
-
2016-08-11
Terms of use
- Copyright holder:
- Association for Computing Machinery
- Copyright date:
- 2016
- Rights statement:
- Copyright © 2016 ACM. This is the accepted manuscript version of the article. The final version is available online from ACM at: https://doi.org/10.1145/2857050
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Association for Computing Machinery at https://dx.doi.org/10.1145/2857050
If you are the owner of this record, you can report an update to it here: Report update to this record