On the Counting Complexity of the Skolem Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908475941978112 |
|---|---|
| author | Jindal, Gorav Ouaknine, Joël |
| author_facet | Jindal, Gorav Ouaknine, Joël |
| contents | The Skolem Problem asks, given an integer linear recurrence sequence (LRS), to determine whether the sequence contains a zero term or not. Its decidability is a longstanding open problem in theoretical computer science and automata theory. Currently, decidability is only known for LRS of order at most 4. On the other hand, the sole known complexity result is NP-hardness, due to Blondel and Portier.
A fundamental result in this area is the celebrated Skolem-Mahler-Lech theorem, which asserts that the zero set of any LRS is the union of a finite set and finitely many arithmetic progressions. This paper focuses on a computational perspective of the Skolem-Mahler-Lech theorem: we show that the problem of counting the zeros of a given LRS is #P-hard, and in fact #P-complete for the instances generated in our reduction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_00098 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Counting Complexity of the Skolem Problem Jindal, Gorav Ouaknine, Joël Computational Complexity Logic in Computer Science F.1.3; F.1.1 The Skolem Problem asks, given an integer linear recurrence sequence (LRS), to determine whether the sequence contains a zero term or not. Its decidability is a longstanding open problem in theoretical computer science and automata theory. Currently, decidability is only known for LRS of order at most 4. On the other hand, the sole known complexity result is NP-hardness, due to Blondel and Portier. A fundamental result in this area is the celebrated Skolem-Mahler-Lech theorem, which asserts that the zero set of any LRS is the union of a finite set and finitely many arithmetic progressions. This paper focuses on a computational perspective of the Skolem-Mahler-Lech theorem: we show that the problem of counting the zeros of a given LRS is #P-hard, and in fact #P-complete for the instances generated in our reduction. |
| title | On the Counting Complexity of the Skolem Problem |
| topic | Computational Complexity Logic in Computer Science F.1.3; F.1.1 |
| url | https://arxiv.org/abs/2403.00098 |