On the complexity of the orbit problem
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...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Association for Computing Machinery
2016
|
| _version_ | 1797087716587864064 |
|---|---|
| author | Chonev, V Ouaknine, J Worrell, J |
| author_facet | Chonev, V Ouaknine, J Worrell, J |
| author_sort | Chonev, V |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T02:39:40Z |
| format | Journal article |
| id | oxford-uuid:a9ff7ec8-83ed-427c-8c5d-fb5012b2bc9b |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:39:40Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:a9ff7ec8-83ed-427c-8c5d-fb5012b2bc9b2022-03-27T03:12:12ZOn the complexity of the orbit problemJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:a9ff7ec8-83ed-427c-8c5d-fb5012b2bc9bSymplectic Elements at OxfordAssociation for Computing Machinery2016Chonev, VOuaknine, JWorrell, JWe 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. |
| spellingShingle | Chonev, V Ouaknine, J Worrell, J On the complexity of the orbit problem |
| title | On the complexity of the orbit problem |
| title_full | On the complexity of the orbit problem |
| title_fullStr | On the complexity of the orbit problem |
| title_full_unstemmed | On the complexity of the orbit problem |
| title_short | On the complexity of the orbit problem |
| title_sort | on the complexity of the orbit problem |
| work_keys_str_mv | AT chonevv onthecomplexityoftheorbitproblem AT ouakninej onthecomplexityoftheorbitproblem AT worrellj onthecomplexityoftheorbitproblem |