Source-linked AI summary
A note on the $Σ_2^P$-completeness of the Frobenius number
Thomas Rothvoss
TL;DR
The paper addresses the difficult-to-verify claim that deciding whether the Frobenius number exceeds a threshold is Σ_2^P-complete. It provides a write-up of Matsubara’s proof, reducing Q3DM to a Frobenius instance through a base-(n+1) construction. The proof establishes the claimed completeness while noting a minor syntactic-complement caveat.
Problem
Matsubara’s claimed Σ_2^P-completeness result for deciding whether g(A)≥k lacked formal publication and was difficult to verify.
Method
The note reduces Q3DM to FROB by encoding vertices and edges in base b=n+1 and proving representability in both directions.
Results
The construction proves that a Q3DM instance is affirmative exactly when the corresponding Frobenius instance belongs to FROB, supporting the claimed Σ_2^P-completeness.
Takeaways & Limitations
The note clarifies the completeness proof for the decision version of the Frobenius problem.
Takeaways & Limitations
The complement discussion ignores syntactically invalid instances, treating them as a polynomial-time recognizable difference irrelevant for complexity purposes.
Abstract
from arXiv · showhide
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).
1 Introduction
The note introduces the Frobenius number and its decision problem, situating the claimed Σ_2^P-completeness result within a history of complexity results and verification difficulties.
- 1 Introduction: For gcd(A)=1, Schur’s Theorem implies that all sufficiently large integers are A-representable, so g(A) is the largest non-representable integer.The example g({5, 6})=19 illustrates this definition.
- 1 Introduction: The Frobenius number is equivalent to the coin problem of finding the largest amount unavailable from given coin denominations.
- 1 Introduction: Kannan proved that g(A) is computable in polynomial time when the number of elements in A is fixed.The note instead focuses on the complexity-theoretic setting where the dimension is not fixed.
- 1 Introduction: Ramírez-Alfonsín established that FROB is NP-hard under Turing reductions, after which Matsubara stated its exact classification.
- 1 Introduction: Because Matsubara’s 2016 result lacked formal publication and was difficult to verify, this note clarifies the completeness proof.
2 Preliminaries
The preliminaries define the polynomial-hierarchy classes and reductions used later, then introduce Q3DM as the hard problem for the proof.
- 2 Preliminaries: Σ_2^P consists of languages expressible with an existential polynomial-length witness followed by a universal polynomial-length witness checked in polynomial time.
- 2 Preliminaries: Π_2^P reverses the quantifier order, using a universal witness followed by an existential witness in a polynomial-time predicate.
- 2 Preliminaries: Σ_2^P and Π_2^P are complementary through language complementation, and both extend to higher levels with additional alternating quantifiers.
- 2 Preliminaries: A polynomial-time many-one reduction maps instances via a polynomial-time computable function, and Σ_2^P-hardness requires every language in Σ_2^P to reduce to the target.
- 2 Preliminaries: The proof uses transitivity of polynomial reductions to establish hardness from a suitable complete problem.
- 2 Preliminaries: Q3DM asks whether every subset S1 of M1 can be completed by some subset S2 of M2 into a perfect matching.The quantifier pattern is ∀S1 ⊆M1 ∃S2 ⊆M2.
3 The main result
The note establishes the claimed complexity result by reducing quantified 3-dimensional matching to the complementary Frobenius language. Its construction uses base-b digit encodings to make representability equivalent to completing every M1 choice with an M2 matching.
- Complexity formulation: The proof works with the complementary language (A, k): g(A) < k, while syntactically invalid instances are handled by a polynomial-time check.This complement is sufficient for the complexity argument because the relevant validity distinction is polynomial-time recognizable.
- Reduction construction: The reduction starts from Q3DM, indexes the 3n vertices and M1 edges as digit positions, and sets the base to b = n + 1.The construction assumes equal vertex-set sizes, takes M1 to be a matching, and maps vertices to positions 0 through 3n − 1.
- Reduction construction: Each constructed number has a sparse b-ary representation: at most five non-zero digits for A1 numbers and at most four for A2 numbers.The encoding length and the size of A remain polynomial because m ≤ n^3.
- Correctness proof: For the forward direction, a perfect matching extending S1 selects one number per matching edge whose digit contributions reproduce every target digit without carry-over.Exactly n numbers are selected; vertex positions receive their designated contributions, while the edge-position digit receives n.
- Correctness proof: For the converse, representing the constructed target forces at most n summands, exactly n distinct edge witnesses, and no carry-over, yielding a perfect matching whose M1 part is S1.The no-slack argument makes coefficients Boolean and identifies the remaining edges as an S2 subset of M2.