文章基本信息

标题：Near-Optimal Complexity Bounds for Fragments of the Skolem Problem
本地全文：下载
作者：S. Akshay ; Nikhil Balaji ; Aniket Murhekar 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：37:1-37:18
DOI：10.4230/LIPIcs.STACS.2020.37
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Linear Recurrences; Skolem problem; NP-completeness; Weighted automata