27 citations · 61 across the 8 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.CC2016
The Complexity of the Numerical Semigroup Gap Counting Problem
Shunichi Matsubara
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 nonn…
cs.CC2016★ 3 cited
The Computational Complexity of the Frobenius Problem
Shunichi Matsubara
In this paper, as a main theorem, we prove that the decision version of the Frobenius problem is Sigma_2^P-complete under Karp reductions.Given a finite set A of coprime positive i…