Chennai Mathematical Institute

Seminars




2.00 pm, Seminar Hall
Low complexity variants of Skolem and positivity problems

Nikhil Balaji
Aalen University, Germany.
07-08-17


Abstract

Given a linear recurrence sequence (LRS), the Skolem problem, asks whether it ever becomes zero. The decidability status 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 from a 2003 paper of Blondel and Portier.

In this talk, I'll give a different proof of this result, which is arguably simpler and interestingly yields a subclass of LRS for which the Skolem problem which is NP-complete. I'll also mention a few open problems closely related to the Skolem problem.

Based on joint work with S. Akshay and Nikhil Vyas.