Pith. Sign in

REVIEW

A note on the $\Sigma_2^P$-completeness of the Frobenius number

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Thomas Rothvoss

Computational Complexity · Submitted 30 Aug 2026 · 6 references

Pith's verdict: A clean, readable write-up of Matsubara's Sigma_2^P-completeness proof for the Frobenius number decision problem, but the load-bearing carry-freeness argument in Claim II needs a tighter justification before the result can be considered fully verified.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 9, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 1 major objection · 3 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2608.30036 (version 1)
Pith IDNVEDT5JY, Pith's permanent record of this paper and its review
CitationThomas Rothvoss. "A note on the $\Sigma_2^P$-completeness of the Frobenius number." arXiv:2608.30036 (2026). https://pith.science/paper/NVEDT5JY
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The Frobenius number decision problem is Σ_2^P-complete, placing it exactly on the second level of the polynomial hierarchy.

The reading

The paper establishes that deciding whether the Frobenius number of a given set of integers is at least a given threshold is complete for the complexity class Σ_2^P—the second level of the polynomial hierarchy. This means the problem is exactly as hard as any problem solvable with an 'exists-forall' quantifier structure in polynomial time. The proof reduces the known Π_2^P-complete problem Quantified 3-Dimensional Matching to the complement of the Frobenius decision problem, using a base-representation encoding that avoids carries. The paper serves as a clarifying write-up of a result originally due to Matsubara (2016) that had not yet appeared in a peer-reviewed venue.

What carries the argument

The central object is a base-b encoding of edges as integers, with b = n+1, where n is the number of vertices in each part of the 3D matching. Each edge e from M1 or M2 is represented by an integer a = $b^{{3n+m}}$ plus contributions to vertex-digit positions and, for edges in M1, an extra digit for the edge index. The threshold k = n $b^{{3n+m}}$ forces exactly n numbers to be used, mimicking a perfect matching. The construction ensures that sums correspond exactly to the characteristic vector of a matching, with no carry-over because the base exceeds any digit sum.

Extended reading notes

Core claim

The paper's central finding is that the language FROB = {(A, k) : g(A) ≥ k} is Σ_2^P-complete. This classification places the Frobenius number decision problem precisely on the second level of the polynomial hierarchy, settling its exact complexity. The proof uses a polynomial-time reduction from the Π_2^P-complete Quantified 3-Dimensional Matching (Q3DM) to the complement FROB = {(A, k) : g(A) < k}. The construction encodes Q3DM instances into a set of integers A and a threshold k such that a perfect matching exists if and only if all sufficiently large integers are representable by A. The encoding ensures no carry-over in base b = n+1 representation, a critical technical detail.

Load-bearing premise

The hardness proof relies on the assumption that Quantified 3-Dimensional Matching (Q3DM) is Π_2^P-complete, as established by McLoughlin (1984). If this completeness result were incorrect or required different input encoding, the reduction would not establish Σ_2^P-hardness.

Editorial extensions

If this is right

  • The Frobenius number decision problem is not in NP unless the polynomial hierarchy collapses, because Σ_2^P-complete problems are believed harder than NP-complete ones.
  • Computing the exact Frobenius number is also hard: a polynomial-time algorithm for g(A) would solve the decision problem, transferring the Σ_2^P-hardness to the function version.
  • The result provides a natural example of a Σ_2^P-complete problem outside formal logic or game theory, rooted in a classical number-theoretic problem.
  • The proof technique of encoding quantifier alternations via carry-free base representations may be applicable to other natural decision problems with an 'exists-forall' structure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The reduction is sensitive to the choice of base; using a fixed base like binary would introduce carries and likely break the argument, suggesting that the hardness may depend on the ability to control digit sums through a large base.
  • The result does not affect the fixed-dimension case (Kannan's polynomial-time algorithm for constant n), but it shows that when the number of coin denominations is part of the input, the complexity jumps to the second level of the polynomial hierarchy.
  • If the Frobenius number decision problem were later shown to be in NP, that would imply Σ_2^P = NP and thus collapse the polynomial hierarchy, so the classification is robust under standard complexity assumptions.
Original 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) \geq k$ is $\Sigma_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).

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,240 input tokens.

What the abstract itself states, as probabilities: claims first 0.12 · states limitation 0.34 · human participants 0.02 · controlled comparison 0.01 · randomized assignment 0.01 · states quantitative result 0.18 · compares with prior results 0.51 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

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 $\Sigma_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).

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 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$. background 1.00 0.05 0.03 asserted 1.00
s1 In a 2016 preprint, Matsubara states that given $A$ and $k$, deciding if $g(A) \geq k$ is $\Sigma_2^P$-complete. background 0.98 0.03 0.33 asserted 0.98
s2 A decade has passed since without peer-reviewed publication of this result. gap 0.77 0.18 0.04 asserted 1.00
s3 At the same time, the community has found it difficult to verify this result. gap 0.72 0.19 0.03 asserted 1.00
s4 In this note, we give a write-up of the completeness proof based on Matsubara (2016). contribution 1.00 0.93 0.42 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.90 · evidence from proof or derivation 0.92.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. b-ary representation of number a arising from edge ei = (v1,j1 , v2,j2 , v3,j3 ) ∈ M1 (top) and e = (v1,j1 , v2,j2 , v3,j3 ) ∈ M2 (bottom). Here ∗ means any number in {0, . . . , n}. x ≥ k. We need to prove that x is A-representable. We observe that Amin := min{a | a ∈ A} = b 3n+m, attained by setting d1 = d2 = d3 = 0 for a number arising from any edge in M2. It suffices to prove the claim for x with nb3n+m = k ≤ x ≤ k + Amin − 1 = b 3n+m+1 − 1 since we can then add integral multiples of Amin to cover all integers in [k, ∞). Hence we can write x in its b-ary representation as

Figures reproduced from arXiv:2608.30036 by the authors.

References
How the literature uses it

What this paper does with the arXiv papers it cites

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers whose main result relates to this one's

Found among the papers closest to this one by title and main claim. Pith's classifier compared each pair's main results and a second model family confirmed the relation; checked against two further families, shown conflicts agreed 118 times in 120 and shown same results 218 times in 239. The quoted sentence is the other paper's main claim.

States the same result 1 paper
  • 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 integers, we call the greatest integer that cannot be represented as a nonnegative integer combination of A the Frobenius number, and we denote it as g(A).

    The Computational Complexity of the Frobenius Problem · 0.99

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.