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 th...
| Main Authors: | , , |
|---|---|
| פורמט: | Journal article |
| יצא לאור: |
Association for Computing Machinery
2016
|
| נושאים: |
| סיכום: | 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 NP^{RP}. |
|---|