Ventsislav Chonev
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.
- E. Allender, P. Bürgisser, J. Kjeldgaard-Pedersen, and P. B. Miltersen. On the complexity of numerical analysis. SIAM J. Comput., 38(5):1987--2006, 2009. Google Scholar
Digital Library
- V. Arvind and T. Vijayaraghavan. The orbit problem is in the GapL hierarchy. J. Comb. Optim., 21(1):124--137, 2011. Google ScholarDigital Library
- A. Baker and G. Wüstholz. Logarithmic forms and group varieties. Jour. Reine Angew. Math., 442:19--62, 1993.Google Scholar
- A. M. Ben-Amram, S. Genaim, and A. N. Masud. On the termination of integer loops. ACM Trans. Program. Lang. Syst., 34(4):16, 2012. Google ScholarDigital Library
- J. Berstel and M. Mignotte. Deux propriétés décidables des suites récurrentes linéaires. Bulletin de la Société Mathématique de France, 104, 1976.Google Scholar
- P. Blanksby and H. Montgomery. Algebraic integers near the unit circle. Acta Arith., pages 355--369, 1971.Google ScholarCross Ref
- V. Blondel and N. Portier. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra and Its Applications, 2002.Google Scholar
- M. Braverman. Termination of integer linear programs. In CAV, volume 4144 of Lecture Notes in Computer Science, pages 372--385. Springer, 2006. Google ScholarDigital Library
- Y. Bugeaud. Linear forms in p-adic logarithms and the diophantine equation (x^n - 1)/(x - 1) = y^q. Math. Proc. Cambridge Phil. Soc., 127:373--381, 1999.Google ScholarCross Ref
- J.-Y. Cai. Computing Jordan normal forms exactly for commuting matrices in polynomial time. Int. J. Found. Comput. Sci., 5(3/4):293--302, 1994.Google ScholarCross Ref
- V. Chonev, J. Ouaknine, and J. Worrell. The Orbit Problem in higher dimensions (long version). CoRR, arXiv:1303.2981, 2013. Google ScholarDigital Library
- H. Cohen. A Course in Computational Algebraic Number Theory. Springer, 1993. Google ScholarDigital Library
- E. Hainry. Reachability in linear dynamical systems. In CiE, volume 5028 of Lecture Notes in Computer Science, pages 241--250. Springer, 2008. Google ScholarDigital Library
- V. Halava, T. Harju, M. Hirvensalo, and J. Karhumaki. Skolem's problem -- on the border between decidability and undecidability. TUCS Technical Report, (683), 2005.Google Scholar
- P. Halmos. Finite-Dimensional Vector Spaces. Springer, 1974.Google ScholarCross Ref
- G. Hansel. Une démonstration simple du théorème de Skolem-Mahler-Lech. Theoretical Computer Science, 43:91 -- 98, 1986. Google ScholarDigital Library
- M. Harrison. Lectures on sequential machines. Academic Press, Orlando, 1969. Google ScholarDigital Library
- M. Hirvensalo, J. Karhumaki, and A. Rabinovich. Computing partial information out of intractable: Powers of algebraic numbers as an example. Journal of Number Theory, 130:232--253, 2010.Google ScholarCross Ref
- R. Kannan and R. J. Lipton. The orbit problem is decidable. In Proceedings of the twelfth annual ACM symposium on Theory of computing, STOC '80, pages 252--261, New York, NY, USA, 1980. ACM. Google ScholarDigital Library
- R. Kannan and R. J. Lipton. Polynomial-time algorithm for the orbit problem. J. ACM, 33(4):808--821, 1986. Google ScholarDigital Library
- C. Lech. A note on recurring series. Arkiv för Matematik, 2:417--421, 1953.Google Scholar
- K. Mahler. Eine arithmetische Eigenschaft der Taylor-Koeffizienten rationaler Funktionen. Proc. Akad. Wet. Amsterdam, 38:51--60, 1935.Google Scholar
- M. Mignotte. Some useful bounds. Computer Algebra, pages 259--263, 1982.Google ScholarCross Ref
- M. Mignotte, T. Shorey, and R. Tijdeman. The distance between terms of an algebraic recurrence sequence. Jour. Reine Angew. Math., 349:63 -- 76, 1984.Google Scholar
- J. Ouaknine and J. Worrell. Decision problems for linear recurrence sequences. In RP, volume 7550 of Lecture Notes in Computer Science, pages 21--28, 2012. Google ScholarDigital Library
- V. Pan. Optimal and nearly optimal algorithms for approximating polynomial zeros. Computers & Mathematics with Applications, 31(12):97 -- 138, 1996.Google ScholarCross Ref
- A. Schönhage. On the power of random access machines. In H. Maurer, editor, Automata, Languages and Programming, volume 71 of Lecture Notes in Computer Science, pages 520--529. Springer, 1979. Google ScholarDigital Library
- T. Skolem. Ein Verfahren zur Behandlung gewisser exponentialer Gleichungen und diophantischer Gleichungen. Skand. Mat. Kongr., 8:163--188, 1934.Google Scholar
- S. P. Tarasov and M. N. Vyalyi. Orbits of linear maps and regular languages. CoRR, arXiv:1011.1842, 2010. Google ScholarDigital Library
- R. Tijdeman. Some applications of diophantine approximation. Number Theory for the Millennium III, pages 261--284, 2002.Google Scholar
- A. Tiwari. Termination of linear programs. In CAV, volume 3114 of Lecture Notes in Computer Science, pages 70--82. Springer, 2004.Google Scholar
- A. J. van der Poorten. Linear forms in logarithms in the p-adic case. Transcendence Theory: Advances and Applications, pages 29--57, 1977.Google Scholar
- N. Vereshchagin. Occurrence of zero in a linear recursive sequence. Mathematical Notes, 38:609--615, 1985.Google ScholarCross Ref
- J.-Yi Cai, R. J. Lipton, and Y. Zalcstein. The complexity of the A B C problem. SIAM J. Comput., 29(6):1878--1888, 2000. Google ScholarDigital Library
Index Terms
- The orbit problem in higher dimensions
Recommendations
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 ν may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by ...
The orbit problem is in the GapL hierarchy
The Orbit problem is defined as follows: Given a matrix A n n and vectors x , y n , does there exist a non-negative integer i such that A i x = y . This problem was shown to be in deterministic polynomial time by Kannan and ...
Complete Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem
The Orbit Problem consists of determining, given a matrix A on ?d$\mathbb {Q}^{d}$, together with vectors x and y, whether the orbit of x under repeated applications of A can ever reach y. This problem was famously shown to be decidable by Kannan and ...
Comments