  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.
