License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.78
URN: urn:nbn:de:0030-drops-81306
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8130/
Go to the corresponding LIPIcs Volume Portal

S., Akshay ; Balaji, Nikhil ; Vyas, Nikhil

Complexity of Restricted Variants of Skolem and Related Problems

pdf-format:
LIPIcs-MFCS-2017-78.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{s_et_al:LIPIcs:2017:8130,
  author =	{Akshay S. and Nikhil Balaji and Nikhil Vyas},
  title =	{{Complexity of Restricted Variants of Skolem and Related Problems}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{78:1--78:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8130},
  URN =		{urn:nbn:de:0030-drops-81306},
  doi =		{10.4230/LIPIcs.MFCS.2017.78},
  annote =	{Keywords: Linear recurrence sequences, Skolem problem, NP-completeness, Program termination}
}

Keywords: Linear recurrence sequences, Skolem problem, NP-completeness, Program termination
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI