Document Open Access Logo

Complexity of Restricted Variants of Skolem and Related Problems

Authors Akshay S., Nikhil Balaji, Nikhil Vyas

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.78.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Akshay S.
Nikhil Balaji
Nikhil Vyas

Cite AsGet BibTex

Akshay S., Nikhil Balaji, and Nikhil Vyas. Complexity of Restricted Variants of Skolem and Related Problems. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.78

Abstract

Given a linear recurrence sequence (LRS), the Skolem problem, asks whether it ever becomes zero. The decidability of this problem has been open for several decades. Currently decidability is known only for LRS of order upto 4. For arbitrary orders (i.e., number of terms the n-th depends on), the only known complexity result is NP-hardness by a result of Blondel and Portier from 2002. In this paper, we give a different proof of this hardness result, which is arguably simpler and pinpoints the source of hardness. To demonstrate this, we identify a subclass of LRS for which the Skolem problem is in fact NP-complete. We show the generic nature of our lower-bound technique by adapting it to show stronger lower bounds of a related problem that encompasses many known decision problems on linear recurrent sequences.
Keywords
  • Linear recurrence sequences
  • Skolem problem
  • NP-completeness
  • Program termination

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Manindra Agrawal, S. Akshay, Blaise Genest, and P. S. Thiagarajan. Approximate verification of the symbolic dynamics of markov chains. J. ACM, 62(1):2:1-2:34, 2015. Google Scholar
  2. S. Akshay, Timos Antonopoulos, Joël Ouaknine, and James Worrell. Reachability problems for markov chains. Inf. Process. Lett., 115(2):155-158, 2015. Google Scholar
  3. S. Akshay, Blaise Genest, Bruno Karelovic, and Nikhil Vyas. On regularity of unary probabilistic automata. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 8:1-8:14, 2016. Google Scholar
  4. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  5. M. Artin. Algebra. Pearson Prentice Hall, 2011. URL: https://books.google.de/books?id=QsOfPwAACAAJ.
  6. Amir M. Ben-Amram, Samir Genaim, and Abu Naser Masud. On the termination of integer loops. ACM Trans. Program. Lang. Syst., 34(4):16:1-16:24, December 2012. Google Scholar
  7. V. D. Blondel and N. Portier. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. In Linear Algebra and its Applications, pages 351-352. Elsevier, 2002. Google Scholar
  8. Mark Braverman. Termination of integer linear programs. In Computer Aided Verification, 18th International Conference, CAV 2006, Seattle, WA, USA, August 17-20, 2006, Proceedings, pages 372-385, 2006. Google Scholar
  9. Ventsislav Chonev, Joël Ouaknine, and James Worrell. The polyhedron-hitting problem. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 940-956, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.64.
  10. Ventsislav Chonev, Joël Ouaknine, and James Worrell. On the complexity of the orbit problem. J. ACM, 63(3):23:1-23:18, 2016. URL: http://dx.doi.org/10.1145/2857050.
  11. Henri Cohen. A course in computational algebraic number theory, volume 138. Springer Science &Business Media, 2013. Google Scholar
  12. Graham Everest, Alfred J. van der Poorten, Igor E. Shparlinski, and Thomas Ward. Recurrence Sequences, volume 104 of Mathematical surveys and monographs. American Mathematical Society, 2003. URL: http://www.ams.org/bookstore?fn=20&arg1=survseries&item=SURV-104.
  13. Godfrey H. Hardy and Edward M. Wright. An introduction to the theory of numbers (5. ed.). Clarendon Press, 1995. Google Scholar
  14. Dan Kalman. The generalized vandermonde matrix. Mathematics Magazine, 57(1):15-21, 1984. Google Scholar
  15. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972. Google Scholar
  16. Joël Ouaknine, João Sousa Pinto, and James Worrell. On termination of integer linear loops. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 957-969, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.65.
  17. Joël Ouaknine and James Worrell. Decision problems for linear recurrence sequences. In Reachability Problems - 6th International Workshop, RP 2012, Bordeaux, France, September 17-19, 2012. Proceedings, pages 21-28, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33512-9_3.
  18. Joël Ouaknine and James Worrell. On the positivity problem for simple linear recurrence sequences,. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 318-329, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_27.
  19. Joël Ouaknine and James Worrell. Positivity problems for low-order linear recurrence sequences. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 366-379, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.27.
  20. Joël Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 330-341, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_28.
  21. Joël Ouaknine and James Worrell. On linear recurrence sequences and loop termination. SIGLOG News, 2(2):4-13, 2015. Google Scholar
  22. Marcus Schaefer and Christopher Umans. Completeness in the polynomial-time hierarchy: A compendium. SIGACT news, 33(3):32-49, 2002. Google Scholar
  23. Ashish Tiwari. Termination of linear programs. In Computer Aided Verification, 16th International Conference, CAV 2004, Boston, MA, USA, July 13-17, 2004, Proceedings, pages 70-82, 2004. Google Scholar
  24. Prasoon Tiwari. A problem that is easier to solve on the unit-cost algebraic RAM. J. Complexity, 8(4):393-397, 1992. URL: http://dx.doi.org/10.1016/0885-064X(92)90003-T.
  25. M.Hirvensalo V.Halava, T.Harju and J.Karhumäki. Skolem’s problem on the border between decidability and undecidability. In TUCS Technical Report Number 683, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact