Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 1 min ago
PreprintarXiv licencearXiv

A note on the Σ2P-completeness of the Frobenius number

  • Thomas Rothvoss
Open at sourcePDFDOICite

Abstract

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) ≥ k is Σ2P-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).

Related

  1. A Sharp Upper Bound for the Frobenius Number
    Lin Chen, Tingwei Hu, Yuchen Mao +1
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. A note on the logarithmic exponent of Ramsey number r(4,t)
    Kaizhe Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A note on the list chromatic number of two matroids
    Bence Garami
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Frobenius and quasi-Frobenius left Hopf algebroids
    Sophie Chemla
    Journal of Pure and Applied AlgebraPeer-reviewedCC BYAlgebra & number theoryHAL
  5. Frobenius splitting for Fano threefolds
    Hiromu Tanaka
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{rothvoss2026note,
  title = {{A note on the $Σ_2^P$-completeness of the Frobenius number}},
  author = {Thomas Rothvoss},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.30036},
  eprint = {2608.30036},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.30036},
}
RIS
TY  - UNPB
TI  - A note on the Σ_2^P-completeness of the Frobenius number
AU  - Thomas Rothvoss
PY  - 2026
DA  - 2026/08/30
PB  - arXiv
DO  - 10.48550/arxiv.2608.30036
UR  - https://arxiv.org/abs/2608.30036
AB  - 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) ≥ 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).
ER  -