research-article

Open access

On the Complexity of the Orbit Problem

Authors:

Ventsislav Chonev,

Joël Ouaknine,

James WorrellAuthors Info & Claims

Journal of the ACM (JACM), Volume 63, Issue 3

Article No.: 23, Pages 1 - 18

https://doi.org/10.1145/2857050

Published: 22 June 2016 Publication History

Abstract

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 Kannan and Lipton in the 1980s, we show that when ν has dimension one, this problem is solvable in polynomial time, and when ν has dimension two or three, the problem is in NP^RP.

Supplementary Material

a23-chonev-apndx.pdf (chonev.zip)

Supplemental movie, appendix, image and software files for, On the Complexity of the Orbit Problem

Download
235.49 KB

References

[1]

V. Arvind and T. Vijayaraghavan. 2011. The orbit problem is in the GapL hierarchy. J. Comb. Optim. 21, 1 (2011), 124--137.

Digital Library

[2]

Alan Baker. 1975. Transcendental Number Theory. Cambridge University Press, Cambridge.

[3]

A. Baker and G. Wüstholz. 1993. Logarithmic forms and group varieties. J. Reine Angew. Math. 442 (1993), 19--62.

[4]

Amir M. Ben-Amram, Samir Genaim, and Abu Naser Masud. 2012. On the termination of integer loops. ACM Trans. Program. Lang. Syst. 34, 4 (2012), 16.

Digital Library

[5]

Jean Berstel and Maurice Mignotte. 1976. Deux propriétés décidables des suites récurrentes linéaires. Bull. Soc. Math. France 104 (1976), 175--184.

[6]

P. Blanksby and H. Montgomery. 1971. Algebraic integers near the unit circle. Acta Arith. (1971), 355--369.

[7]

V. D. Blondel and N. Portier. 2002. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra and Its Applications 351 (2002), 91--98.

[8]

M. Braverman. 2006. Termination of integer linear programs. In Proceedings of the 18th International Conference on Computer Aided Verification (CAV, LNCS 4144). Springer, Berlin, 372--385.

Digital Library

[9]

Jin-yi Cai, Richard J. Lipton, and Yechezkel Zalcstein. 2000. The complexity of the ABC problem. SIAM J. Comput. 29, 6 (2000), 1878--1888.

Digital Library

[10]

Ventsislav Chonev, Joël Ouaknine, and James Worrell. 2013. The orbit problem in higher dimensions. In STOC. ACM, New York, NY, 941--950.

Digital Library

[11]

Ventsislav Chonev, Joël Ouaknine, and James Worrell. 2015. The polyhedron-hitting problem. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). SIAM, Philadelphia, PA, 940--956. http://dl.acm.org/citation.cfm?id=2722129.2722193.

Digital Library

[12]

H. Cohen. 1993. A Course in Computational Algebraic Number Theory. Springer, Berlin.

Digital Library

[13]

Graham Everest, Alf van der Poorten, Thomas Ward, and Igor Shparlinski. 2003. Recurrence Sequences. American Mathematical Society, Washington DC.

[14]

Emmanuel Hainry. 2008. Reachability in linear dynamical systems. In Logic and Theory of Algorithms. Springer, Berlin, 241--250.

Digital Library

[15]

V. Halava, T. Harju, M. Hirvensalo, and J. Karhumäki. 2005. Skolem’s Problem -- On the Border between Decidability and Undecidability. Technical Report 683. Turku Centre for Computer Science.

[16]

G. Hansel. 1986. Une démonstration simple du théorème de Skolem-Mahler-Lech. Theor. Comput. Sci. 43 (1986), 91--98.

[17]

Michael A. Harrison. 1969. Lectures on Linear Sequential Machines. Academic Press, New York, NY.

Digital Library

[18]

R. Kannan and R. Lipton. 1986. Polynomial-time algorithm for the orbit problem. J. ACM 33, 4 (1986), 808--821.

Digital Library

[19]

Ravindran Kannan and Richard J. Lipton. 1980. The orbit problem is decidable. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, NY, 252--261.

Digital Library

[20]

L. Kronecker. 1875. Zwei sätze über gleichungen mit ganzzahligen koeffizienten. J. Reine Angew. Math. 53 (1875), 173--175.

[21]

Christer Lech. 1953. A note on recurring series. Arkiv för Matematik 2 (1953), 417--421.

[22]

A. K. Lenstra, H. W. Lenstra, and L. Lovász. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), 515--534.

[23]

B. Litow. 1997. A decision method for the rational sequence problem. In Electronic Colloquium on Computational Complexity (ECCC), Vol. 4.

[24]

K. Mahler. 1935. Eine arithmetische eigenschaft der Taylor-koeffizienten rationaler funktionen. Proc. Akad. Wet. Amsterdam 38 (1935), 51--60.

[25]

K. Mahler and J. W. S. Cassels. 1956. On the Taylor coefficients of rational functions. Math. Proc. Cambr. Philos. Soc. 52 (1 1956), 39--48. Issue 01.

[26]

M. Mignotte. 1982. Some useful bounds. Comput. Algebr. (1982), 259--263.

[27]

M. Mignotte, T. Shorey, and R. Tijdeman. 1984. The distance between terms of an algebraic recurrence sequence. Jour. Reine Angew. Math. 349 (1984), 63--76.

[28]

Joël Ouaknine and James Worrell. 2012. Decision problems for linear recurrence sequences. In Reachability Problems, Alain Finkel, Jérôme Leroux, and Igor Potapov (Eds.). Lecture Notes in Computer Science, Vol. 7550. Springer, Berlin, 21--28.

Digital Library

[29]

V. Pan. 1996. Optimal and nearly optimal algorithms for approximating polynomial zeros. Comput. Math. Appl. 31, 12 (1996), 97--138.

[30]

Arto Salomaa and Matti Soittola. 1978. Automata—Theoretic Aspects of Formal Power Series. Springer-Verlag, Berlin.

Digital Library

[31]

Arnold Schönhage. 1979. On the power of random access machines. In Automata, Languages and Programming, Hermann Maurer (Ed.). Lecture Notes in Computer Science, Vol. 71. Springer, Berlin, 520--529.

Digital Library

[32]

Th. Skolem. 1934. Ein verfahren zur behandlung gewisser exponentialer gleichungen und diophantischer gleichungen. Skand. Mat. Kongr. 8 (1934), 163--188.

[33]

I. Stewart and D. Tall. 2002. Algebraic Number Theory and Fermat’s Last Theorem (3rd ed.). A. K. Peters.

[34]

T. Tao. 2008. Structure and Randomness: Pages from Year One of a Mathematical Blog. American Mathematical Society, Washington, DC.

Digital Library

[35]

Sergey Tarasov and Mikhail Vyalyi. 2011. Orbits of linear maps and regular languages. In Computer Science -- Theory and Applications, Alexander Kulikov and Nikolay Vereshchagin (Eds.). Lecture Notes in Computer Science, Vol. 6651. Springer, Berlin, 305--316.

Digital Library

[36]

Ashish Tiwari. 2004. Termination of linear programs. In Computer Aided Verification. Springer, Berlin, 70--82.

[37]

Alfred Jacobus van der Poorten. 1977. Linear forms in logarithms in the p-adic case. Transcend. Theor. Adv. Appl. (1977), 29--57.

[38]

N. Vereshchagin. 1985. Occurrence of zero in a linear recursive sequence. Math. Notes 38 (1985), 609--615.

[39]

Richard Zippel. 1997. Zero testing of algebraic functions. Inform. Process. Lett. 61, 2 (1997), 63--67.

Digital Library

Cited By

García JGómez CLuca F(2024)Solving Skolem's problem for the k–generalized Fibonacci sequence with negative indicesJournal of Number Theory10.1016/j.jnt.2023.10.017257(273-299)Online publication date: Apr-2024
https://doi.org/10.1016/j.jnt.2023.10.017
Bell PHirvensalo MPotapov I(2024) The membership problem for subsemigroups of is NP-complete Information and Computation10.1016/j.ic.2023.105132296(105132)Online publication date: Jan-2024
https://doi.org/10.1016/j.ic.2023.105132
Lefaucheux EOuaknine JPurser DWorrell J(2024)Porous invariants for linear systemsFormal Methods in System Design10.1007/s10703-024-00444-363:1-3(235-271)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10703-024-00444-3
Show More Cited By

Index Terms

On the Complexity of the Orbit Problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Generating functions

Recommendations

The orbit problem in higher dimensions
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

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 ...
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 ⁿ, does there exist a non-negative integer i such that A ⁱ x = y . This problem was shown to be in deterministic polynomial time by Kannan and ...
Parameterized complexity of k-Chinese Postman Problem

We consider the following problem called the k-Chinese Postman Problem (k-CPP): given a connected edge-weighted graph G and integers p and k, decide whether there are at least k closed walks such that every edge of G is contained in at least one of them ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 63, Issue 3

September 2016

303 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2957788

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2016

Accepted: 01 December 2015

Revised: 01 November 2015

Received: 01 April 2014

Published in JACM Volume 63, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

ERC

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
1,159
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)9

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

García JGómez CLuca F(2024)Solving Skolem's problem for the k–generalized Fibonacci sequence with negative indicesJournal of Number Theory10.1016/j.jnt.2023.10.017257(273-299)Online publication date: Apr-2024
https://doi.org/10.1016/j.jnt.2023.10.017
Bell PHirvensalo MPotapov I(2024) The membership problem for subsemigroups of is NP-complete Information and Computation10.1016/j.ic.2023.105132296(105132)Online publication date: Jan-2024
https://doi.org/10.1016/j.ic.2023.105132
Lefaucheux EOuaknine JPurser DWorrell J(2024)Porous invariants for linear systemsFormal Methods in System Design10.1007/s10703-024-00444-363:1-3(235-271)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10703-024-00444-3
Karimov TKelmendi ENieuwveld JOuaknine JWorrell J(2023)The Power of Positivity2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS56636.2023.10175758(1-11)Online publication date: 26-Jun-2023
https://doi.org/10.1109/LICS56636.2023.10175758
Bell PNiskanen RPotapov ISemukhin P(2023)On the Identity and Group Problems for Complex Heisenberg MatricesReachability Problems10.1007/978-3-031-45286-4_4(42-55)Online publication date: 5-Oct-2023
https://doi.org/10.1007/978-3-031-45286-4_4
Lefaucheux EOuaknine JPurser DSharifi M(2023)Model Checking Linear Dynamical Systems under Floating-point RoundingTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-031-30823-9_3(47-65)Online publication date: 22-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30823-9_3
Balaji NNosan KShirmohammadi MWorrell J(2022)Identity Testing for Radical ExpressionsProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533331(1-11)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533331
Almagor SChistikov DOuaknine JWorrell J(2022)O-Minimal Invariants for Discrete-Time Dynamical SystemsACM Transactions on Computational Logic10.1145/350129923:2(1-20)Online publication date: 14-Jan-2022
https://dl.acm.org/doi/10.1145/3501299
Karimov TLefaucheux EOuaknine JPurser DVaronka AWhiteland MWorrell J(2022)What’s decidable about linear loops?Proceedings of the ACM on Programming Languages10.1145/34987276:POPL(1-25)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498727
Bell P(2022)Polynomially ambiguous probabilistic automata on restricted languagesJournal of Computer and System Sciences10.1016/j.jcss.2022.02.002127(53-65)Online publication date: Aug-2022
https://doi.org/10.1016/j.jcss.2022.02.002
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents