{"id":"arxiv/2608.30036","url":"https://arxiv.org/abs/2608.30036","tags":["cs.CC","math.OC"],"score":0,"title":"A note on the $Σ_2^P$-completeness of the Frobenius number","domain":"cs.CC","source":"arxiv","authors":["Thomas Rothvoss"],"reviews":0,"subject":"cs.CC","summary":"Given a finite set $A$ of natural numbers whose greatest common divisor is one, the Frobenius number $g(A)$ is the largest integer that is not a non-negative integer combination of the numbers in $A$. In a 2016 preprint, Matsubara states that given $A$ and $k$, deciding if $g(A) \\geq k$ is $Σ_2^P$-complete. A decade has passed since without peer-reviewed publication of this result. At the same time, the community has found it difficult to verify this result. In this note, we give a write-up of the completeness proof based on Matsubara (2016).","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-30","reactions":{}}