2016/09/21 by Shunichi Matsubara, Matsubara, Shunichi
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1609.06515
openalex publication_date 2016/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.