Conference icon

Conference

The orbit problem in higher dimensions

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. Copyright 2013 ACM.

Actions


Access Document


Publisher copy:
10.1145/2488608.2488728

Authors


Ouaknine, J More by this author
Worrell, J More by this author
Pages:
941-949
Publication date:
2013
DOI:
ISSN:
0737-8017
URN:
uuid:ce170ce7-86a5-45f3-ae96-2a1b32200770
Source identifiers:
411580
Local pid:
pubs:411580
ISBN:
9781450320290

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP