Document Open Access Logo

Near-Optimal Complexity Bounds for Fragments of the Skolem Problem

Authors S. Akshay , Nikhil Balaji , Aniket Murhekar, Rohith Varma, Nikhil Vyas

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.37.pdf
  • Filesize: 0.61 MB
  • 18 pages

Document Identifiers

Author Details

S. Akshay
  • IIT Bombay, India
Nikhil Balaji
  • University of Oxford, UK
Aniket Murhekar
  • University of Illinois, Urbana Champaign, Urbana, IL, USA
Rohith Varma
  • Indian Institute of Technology Palakkad, India
Nikhil Vyas
  • MIT, Cambridge, MA, USA

Funding

This work was partly supported by DST/CEFIPRA/INRIA Associated team EQuaVE.
  • Akshay, S.: Partly supported by DST-INSPIRE Faculty Award [IFA12-MA-17] and SERB Matrices grant MTR/2018/000744.
  • Vyas, Nikhil: Supported by NSF CCF-1909429.

Acknowledgements

This research was supported in part by the International Centre for Theoretical Sciences (ICTS) during a visit for participating in the program - Workshop on Algebraic Complexity Theory (Code: ICTS/wact2019/03).

Cite AsGet BibTex

S. Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, and Nikhil Vyas. Near-Optimal Complexity Bounds for Fragments of the Skolem Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.37

Abstract

Given a linear recurrence sequence (LRS), specified using the initial conditions and the recurrence relation, the Skolem problem asks if zero ever occurs in the infinite sequence generated by the LRS. Despite active research over last few decades, its decidability is known only for a few restricted subclasses, by either restricting the order of the LRS (upto 4) or by restricting the structure of the LRS (e.g., roots of its characteristic polynomial). In this paper, we identify a subclass of LRS of arbitrary order for which the Skolem problem is easy, namely LRS all of whose characteristic roots are (possibly complex) roots of real algebraic numbers, i.e., roots satisfying x^d = r for r real algebraic. We show that for this subclass, the Skolem problem can be solved in NP^RP. As a byproduct, we implicitly obtain effective bounds on the zero set of the LRS for this subclass. While prior works in this area often exploit deep results from algebraic and transcendental number theory to get such effective results, our techniques are primarily algorithmic and use linear algebra and Galois theory. We also complement our upper bounds with a NP lower bound for the Skolem problem via a new direct reduction from 3-CNF-SAT, matching the best known lower bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Linear Recurrences
  • Skolem problem
  • NP-completeness
  • Weighted automata

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, 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, August 21-25, 2017 - Aalborg, Denmark, pages 78:1-78:14, 2017. Google Scholar
  4. 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
  5. Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen. On the complexity of numerical analysis. SIAM J. Comput., 38(5):1987-2006, 2009. URL: https://doi.org/10.1137/070697926.
  6. Alan Baker. Transcendental number theory. Cambridge university press, 1990. Google Scholar
  7. Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, and Filip Mazowiecki. A robust class of linear recurrence sequences. In 28th EACSL Annual Conference on Computer Science Logic, CSL 2020, January 13-16, 2020, Barcelona, Spain, pages 9:1-9:16, 2020. Google Scholar
  8. Paul C Bell, Igor Potapov, and Pavel Semukhin. On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  9. 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
  10. J-Y Cai, Richard J Lipton, Robert Sedgewick, and AC-C Yao. Towards uncheatable benchmarks. In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 2-11. IEEE, 1993. Google Scholar
  11. Jin-yi Cai. Computing Jordan normal forms exactly for commuting matrices in polynomial time. International Journal of Foundations of Computer Science, 5(03n04):293-302, 1994. Google Scholar
  12. 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: https://doi.org/10.1145/2857050.
  13. Henri Cohen. A course in computational algebraic number theory, volume 138. Springer Science & Business Media, 2013. Google Scholar
  14. Abraham De Moivre. The doctrine of chances. In Annotated Readings in the History of Statistics, pages 32-36. Springer, 2001. Google Scholar
  15. Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing, 39(6):2531-2597, 2010. Google Scholar
  16. 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.
  17. Nathanaël Fijalkow, Joël Ouaknine, Amaury Pouly, Jo~ao Sousa-Pinto, and James Worrell. On the decidability of reachability in linear time-invariant systems. In Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control, pages 77-86. ACM, 2019. Google Scholar
  18. Georges Hansel. A simple proof of the Skolem-Mahler-Lech theorem. In International Colloquium on Automata, Languages, and Programming, pages 244-249. Springer, 1985. Google Scholar
  19. Godfrey Harold Hardy, Edward Maitland Wright, et al. An introduction to the theory of numbers. Oxford university press, 1979. Google Scholar
  20. Russell Impagliazzo and Avi Wigderson. P= bpp unless e has subexponential circuits: derandomizing the xor lemma. In Proceedings of the 29th STOC, pages 220-229, 1997. Google Scholar
  21. Donald E Knuth. The art of computer programming. volume 1: Fundamental algorithms. Pearson education, 1997. Google Scholar
  22. Gerardo Lafferriere, George J Pappas, and Shankar Sastry. O-minimal hybrid systems. Mathematics of control, signals and systems, 13(1):1-21, 2000. Google Scholar
  23. Maurice Mignotte. Some useful bounds. In Computer algebra, pages 259-263. Springer, 1983. Google Scholar
  24. Joël Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. In International Colloquium on Automata, Languages, and Programming, pages 330-341. Springer, 2014. Google Scholar
  25. Min Sha. Effective results on the Skolem problem for linear recurrence sequences. Journal of Number Theory, 197:228-249, 2019. Google Scholar
  26. Omid Shakernia, George J Pappas, and Shankar Sastry. Decidable controller synthesis for classes of linear systems. In International Workshop on Hybrid Systems: Computation and Control, pages 407-420. Springer, 2000. Google Scholar
  27. Larry J Stockmeyer and Albert R Meyer. Word problems requiring exponential time (preliminary report). In Proceedings of the fifth annual ACM symposium on Theory of computing, pages 1-9. ACM, 1973. Google Scholar
  28. Terence Tao. Structure and randomness: pages from year one of a mathematical blog. American Mathematical Society Providence, RI, 2008. Google Scholar
  29. Prasoon Tiwari. A problem that is easier to solve on the unit-cost algebraic RAM. J. Complexity, 8(4):393-397, 1992. URL: https://doi.org/10.1016/0885-064X(92)90003-T.
  30. Nikolai Konstantinovich Vereshchagin. Occurrence of zero in a linear recursive sequence. Mathematical Notes, 38(2):609-615, 1985. Google Scholar
  31. 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
  32. F Viete. Opera mathematica. 1579. Reprinted Leiden, Netherlands, 1646, 1970. 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