  In this paper, we prove that the numerical-semigroup-gap counting problem is
#NP-complete as a main theorem. A numerical semigroup is an additive semigroup
over the set of all nonnegative integers. A gap of a numerical semigroup is
defined as a positive integer that does not belong to the numerical semigroup.
The computation of gaps of numerical semigroups has been actively studied from
the 19th century. However, little has been known on the computational
complexity. In 2005, Ramirez-Alfonsin proposed a question whether or not the
numerical-semigroup-gap counting problem is #P-complete. This work is an answer
for his question. For proving the main theorem, we show the #NP-completenesses
of other two variants of the numerical-semigroup-gap counting problem.
